TFS supports many different authentication scenarios.
One of them is the "workgroup mode" where there is no Active Directory domain involved at all, and the users are all using the Windows workgroup authentication mechanism where if the account names and passwords match between the client and server, then the user is authenticated.
Most everything else falls into TFS using Active Directory for domain authentication. Active Directory authentication can be very complex, though, with multiple domains within a forest that may have either one-way or two-way trust relationships.
Now, most of our AD trust and forest needs in TFS are spelled out nicely in Trust and Forests Considerations for Team Foundation Server. If you're having problems, you can use another doc Troubleshooting Team Foundation Server Permissions and Security to help you figure out what's wrong. This can be especially helpful since TFS permissions are managed separately from SharePoint and SQL Reporting Services permission, even though the latter two are part of a TFS install (it'll still be that way in TFS 2008 as well).
What if you're still having trouble? At that point, it's typically best to bisection the problem to figure out if the issue is in Active Directory authentication, or within TFS. A great way of doing that is to manually invoke basically the same AD queries that TFS does, doing that logged in as the TFS service account on the TFS application tier. You can do that with dsquery, a command that comes with Windows Server 2003. Here's a helpful article on some usage scenarios with dsquery.
Which dsquery searches do you want to perform? Matt Hoover, our resident AD expert in TFS, details this in multiple forum threads, but I'll pick one out in particular:
To perform a query against AD that is similar to what the server does use the following command:
dsquery user -samid <account name> -d <domain> | dsget user -dn -samid -sid -display -email -L
The TFSSERVICE account needs to be able to perform this type of query for any user that is added to the system.
Using dsquery, you can divide and conquer the problem - keep invoking dsquery until it starts working, and then if TFS is still broken, you know it's a TFS configuration issue and not a problem in AD 🙂