This problem can be caused by various circumstances, but I most commonly run into it when I reset a virtual machine to a system snapshot that I made months or even years before. When the machine is reset, it is missing all of the automatic password changes that it executed against the domain controller during the intervening months. The password changes are required to maintain the security integrity of the domain.
The trick is to reset computer account password, use netdom.exe or powershell.
netdom.exe resetpwd /s:
Even better (For VM's), avoid the problem altogether by keeping the machine password static. (When appropriate for security, of course.)
DisablePasswordChangeentry from 0 to 1.