How to fix without rejoining to domain: The trust relationship between this workstation and the primary domain failed

Log in as local admin, run the following and then restart.... There are more detailed steps here: http://implbits.com/active-directory/2012/04/13/dont-rejoin-to-fix.html

netdom.exe resetpwd /s:[server] /ud:[user] /pd:*

[server] = a domain controller in the joined domain

[user] = DOMAIN\User format with rights to change the computer password

Worked like a charm for me!