Here's one I hope Google will index so that the next person who comes across this problem can solve it quickly.
I have a Windows 2003 R2 Active Directory domain controller, and have several Linux Samba servers which serve files for Windows users. I had one particular user who would get this error:
[2008/02/22 15:38:54, 0] auth/pampass.c:smb_pam_accountcheck(781)
smb_pam_accountcheck: PAM: Account Validation Failed - Rejecting User DOMAIN\username!
when accessing a Samba server, but is able to access things on the Windows 2k3 server. As it turns out, I hadn't configured PAM properly. In /etc/pam.d/samba I changed it to be:
account required pam_winbind.so
I restarted Samba and things work now.