Every few months, this situation comes up somewhere amongst the plethora of Windows 7 workstations that are managed by my helpdesk. The standard fix is normally to remove the workstation from the domain, and rejoin it again.
I came across a blog post here – http://www.implbits.com/about/blog/tabid/78/post/don-t-rejoin-to-fix-the-trust-relationship-between-this-workstation-and-the-primary-domain-failed/default.aspx – which suggested that this problem was caused by a machine password being corrupted or lost.
A suggested fix for this was to use NETDOM.EXE to reset the machine password. You will need to install the Remote Server Administration Tools from http://go.microsoft.com/fwlink/?LinkID=153874. Once it has been installed, turn the following feature on (from the Turn Windows features on or off applet in the control panel. (you might find some other useful server administrative tools there too!)
From an administrative command prompt, type the following command.
NETDOM resetpwd /s:[domain controller] /ud:[domain admin] /pd:*
[domain controller] = a domain controller in the joined domain
[domain admin] = a domain administrator with administrative rights to the machine
You will be prompted to enter in the password for the domain admin account specified.
Once the command is completed, restart the computer to log in.
NOTE: I did notice that some other settings on the workstation appeared to be corrupted or reset after the reboot. One of these itemms was the Outlook profile, which had to be reset and resynchronized.