This error is caused by the computer password (yes computers have domain passwords) being out of sync with the computer password stored in active directory.
The cause of this occurring can be varied but the scenarios I have involved with are where a computer has been turned off for long periods or when virtual machines are reverted to old snapshots.
In the past the classic fix was to:
- Log-on to the affect computer as a local administrator
- Disconnect the machine from the domain
- Rejoin the machine to the domain
However there is a quicker way though which is to use netdom. Netdom is a tool which should already be present on Windows Server 2008 R2, but on Windows 7 machines may require you to first install the rsat tools.
Fixing the trust relationship is as simple as running the command:
netdom.exe resetpwd /s:<server> /ud:<user> /pd:*
The username you specify must have enough access rights to add a computer onto the domain.