I've run into 'The trust relationship between this workstation and the primary domain failed' a couple of times, and every time I look up the solution I would find blog posts and support articles from Microsoft claiming that you have to rejoin your machine to the domain, however, this is not always possible.

The reason you're seeing this error is because the machine that you are trying to access can no longer securely communicate with the Active Directory domain to which it is joined. The private secret of the machine is no longer set to the same value as the one stored in the domain controller.

Some Microsoft articles will tell you that rejoining the domain will restore the trust relationship. Deleting the computer object and recreating it without a password will also resolve this issue. I, just like the blog post on implbits.com describes, am not a fan of fixes like this.

If you can't simply unjoin and rejoin because, for example, the machine is a CA (Certificate Authority), run this command in Powershell:

Reset-ComputerMachinePassword [-Credential ] [-Server ]

An even better fix would be to change your computer password using netdom, you can do so by running this command:

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

Once the netdom command has been run, you have to reboot the computer and you should no longer see the 'The Trust Relationship Between This Workstation and  the Primary Domain Failed' error.