Sounds like DNS problems to me too. How is your DNS set-up? Has the DC registered its SRV records in the proper places (automatic upon proper configuration)?
Under your forward lookup zone, you should see four folders named _msdcs, _sites, _tcp, _udp. This is where the DC registers its LDAP and Kerberos records. Kerberos, of course, handles client authentication. Any client machine is going to query DNS for these records pronto upon a user logon. If they arent there...well....I've seen things "work" w/o them, but not well, and not forever.
If those arent there you havent got a proper DNS set-up.
Common reasons that they arent registered automatically include...
1) Different AD and DNS forward lookup zone FQDN's. (They can be different in certain situations, but not any you are going to get involved in anytime soon)
2) DC is not a client of a DNS in it's own domain
3) Dynamic updates not enabled on the zone
4) DC is not configured to "register this connections address in DNS" under Advanced TCP/IP properties