Two sets of questions to begin with:

Basic questions:
1. Is it Windows Server 2003 or later, or is it Windows 2000? More precisely, what version of AD/Domain is being used?
2. Are you positive the user is logging on to the domain (or the right one), and not to the local machine?
3. If Windows 2003 and later, what is being entered as a username: "[email protected]" or simply "username". If just "username", back to point 2., can you confirm the third line in the logon screen labeled "Logon To:" is actually showing the proper domain and not local computer?
4. What is the exact wording of the error message?

More advanced:
A. Is the logon failing on one PC only, or on every domain PC?
B. Are other domain users loggin on successfully on those same workstations where this particular user logon is failing?
C. On the Domain Server, checking the properties of the PCs where logon is failing, can you confirm their icon in the AD is not showing a broken connection? It is very unlikely, but it may have happened if you changed the computername without operating in the domain first, for example.
D. Have you re-imaged any of the workstations where the logon is failing?

In general, one way to solve broken domain-workstation link without spending too much time troubleshooting is to remove the workstation from the domain (done at the workstation), then in the domain (on the domain server) - not always needed, but again, it takes 1 second and does not hurt-, then create the workstation again in the domain, the re-join the workstation (at the workstation). Of course, make sure the workstation name you enter in the domain is correct.