It's been a long time since I've been near Active Directory, but the following may help:

1. Check the event log on both client and server, specifically the security section. This may reveal some hints.

2. Make sure the date and time is set properly on the server and client. If these get too out of sync, authentication can fail.

3. Double check the bindings for the computer(s) in question. On the client, this can be checked in a basic way via the GUI, and on the server, the system should show up as a computer object. You can always try to delete the computer server side, then have the client rejoin the domain.

4. Make sure DNS is working properly. Active Directory relies heavily on DNS, and if people point their system to a normal external server (like Google), the domain is likely to fail. Everyone should be pointed at the Windows Server hosting the domain.

There is much more in depth stuff that can be checked, but this should at least cover the basics.