I have AD running on a server 2k3 domain. I recently added a couple of new users. They are unable to access the domain, however. When they try, the get the "system could not log you on, make sure your user name & password are correct,etc" pop up. After I restarted the server, one was able to connect, but the other still was denied. I tried creating a test account, restarted again, and neither the test account nor the legit user account are able to logon. There are no errors in any of the event logs.
Have you tried removing the client PC's from the domain and re-joining them to the domain?
It doesn't matter which PC I try on. However, I think I may have just fixed the problem. A backup Domain Controller was having replication issues. I fixed that, and now the user is able to log on. Not sure why that was the problem, as they should be able to log on with just one Domain Controller authenticating, but there ya go.