Fix: The trust relationship between this workstation and the primary domain failed
This guide is using the NETDOM tool and does not require rejoining the domain

Have you seen this? ’The trust relationship between this workstation and the primary domain failed’
Or this? ‘The security database on the server does not have a computer account for this workstation trust relationship.’ Same issue, different symptom.

I have on multiple occasions beeing a heavy Hyper-V user for my labs…
There are apparently a number of reasons why this happens, but the main reason seems to be lost connection between the ‘client/server’ and the Domain controllers. If the scheduled password change occurs while the server or client is unavailable or has been shut down, then the passwords stored in the server/client and the domain controllers for the computer account mismatch, and you will end up getting this error when trying to logon to the server. It can also appear differently, like if all service accounts stop functioning with events logged as a result, or similar that happens when the server is still running and you have been able to logon or simply never logged off.
The real question…How do we fix it? There are a number of TechNet forum threads on this(added one below as references) and many blog posts allready written, but since I’m always having difficulty finding them myself when I need them, I’ll make my own. Please feel free to borrow this knowledge and reblog/repost it yourself :-) (The guide however, is my own creation…)
The easiest or at least the quickest solution, is to have the server leave the doamin by adding it to a workgroup, then joining it back to the domain again. But, this can sometimes be a bit risky, you may have lots of service account running as domain users and so on, you don’t feel like unkoupling the server from the domain at all, then do this instead.
This guide is taking for granted that you prior to following these steps, have restored connectivity between the server/client and the domain controllers, else this will fail. Resetting the computer password can not be done offline. |
The following steps are performed on a Windows Server 2008 R2 machine, but the same steps apply to Windows Server 2012 |
You log on to your server like you are used to, using your personal domain account:

You type the password and hit enter, then, BAM! This, instead of the normal logon procedure…what a start on a monday morning…

No good…if you don’t like to meddle with server affairs and are the kind of person who likes to stick to your apps once logged into the server, copy the link to this blogpost and send it to someone who can fix it…else, keep reading.
Press OK and then Switch user.

Then use the local server administrator account to logon to the server.

In my case it is one of my SQL boxes, so I type the Servername, Backslash, Local Admin and hit Enter.
Once logged in, you will want to start a PowerShell prompt or a Command prompt with administrative privilieges, ‘as administrator’.

Next, we solve the problem by resetting the Computer password in Active Directory and on the Local machine, for this we use a commande called NETDOM.
Type in the following command:
NETDOM RESETPWD /Server:<name of any domain controller> /UserD:<domain admin account> /PasswordD:<password>
(Yes, the trailing D’s are supposed to be there, don’t ask me why…)
In my prompt it looks a bit like this:

Important! Unlike in this Picture, the domain administrators password will be visible in cleartext, so be careful and close the prompt after you are done! |

Now, we have to do one more thing before order is restored completely, we have to reboot the server. If you don’t, you will still not be able to logon using the domain account.

After the server has rebooted, you are good to go, logon using your regular personal domain account.

Done!
If this did not work out for you, perhaps any of these reference links can be of use for you with additional steps and alternate solutions?
Good luck!
References
NETDOM
http://technet.microsoft.com/en-us/library/cc772217(v=ws.10).aspx
Netdom Overview
http://technet.microsoft.com/sv-se/library/cc737599(v=ws.10).aspx
How to use Netdom.exe to reset machine account passwords of a Windows Server domain controller
http://support.microsoft.com/kb/325850
Don’t rejoin to fix
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
TechNet Forum: The trust relationship between this workstation and the primary domain failed – Windows 7 Enterprise joining 2008 Domain, Error 5722
http://social.technet.microsoft.com/Forums/en-US/w7itpronetworking/thread/8155d5ea-a5c2-4306-8d2b-be3464234460/
TechNet Wiki: Trust Relationship between Workstation and Primary Domain failed
http://social.technet.microsoft.com/wiki/contents/articles/9157.trust-relationship-between-workstation-and-primary-domain-failed.aspx