As with many of my other Administration and Operations posts, this one stems from posts I've seen on the Visual Studio Team System forums. I've read a number of questions where people are having trouble granting their Active Directory users access to their Team Foundation Server.
What I've found is that, oftentimes, this is due to either the trust relationships between their domains or the permissions for the account currently running as the TFS service account. In the latter case, this may be due to using a local account rather than AD account as the service account, AD permission settings, the "Log on as service" permission, or AD trust relationships (looping us back to the first possibility).
So, to help you figure this all out, I'm going to lay down The Word on what it is you need to set up in order to get AD users into TFS.
Hopefully setting that up will let you add your domain users to TFS. If not, though, there may be fouler forces at work. Still, you'll probably want to take a look back at my other post on getting users into TFS entitled "Get your users for nothin' and your sync for free" as our periodic sync process is known to have issues in Whidbey (VSTS 2005) RTM and SP1.
Best of luck, and let me know if you hit any other stumbling blocks along the way!
[Edit: I should note that, from what I can recall of our stated support cases, we permit you to have as many two-way trusts as you like, but only claim to support one one-way trust where the TFS service account must be in the trusted domain.]