Users occasionally see the error 'Trust relationship has been lost with domain controller' when trying to log on to a domain controller. This can happen because of any of the following:

• The secure link between the PC and the Directory is  broken due to a  disruption in the presentation of credentials. If the PC presents the wrong password, the authentication is denied. Each Windows-based computer maintains a machine account password history containing the current and previous passwords used for the account. When two computers attempt to authenticate with each other and a change to the current password is not yet received, Windows then relies on the previous password. If the sequence of password changes exceeds two changes, the computers involved may be unable to communicate, and you may receive error messages (for example, "Access Denied" error messages when Active Directory replication occurs).

• The client machine presents the right password, but the wrong machine account.  If the images that are being used are cloned without properly being SysPrepped, the scenario arises where two machines are presenting the same SIDs, while the passwords are out of sync.   

To resolve this error, reset the password using the Netdom.exe tool included in the Windows Support Tools. The Netdom tool resets the account password on the computer locally (known as a "local secret") and writes this change to the computer's computer account object on a Windows domain controller that resides in the same domain. Simultaneously writing the new password to both places ensures that at least the two computers involved in the operation are synchronized, and starts Active Directory replication so that other domain controllers receive the change.

For detailed instructions on using the Netdom.exe tool, see  the following KB article:
http://support.microsoft.com/kb/260575

You can also remove the client and add it back to the domain to resolve this error.