There’s several different things that can cause the trust relationship issue and there are hundreds of post or more online about the subject. Sometimes simply resetting the computer account in Active Directory can fix the problem. Other times, unjoining/rejoining the computer from the domain will fix the problem. If either of those isn’t the case, usually that is a good indication that there is some sort of corruption in the Active Directory database that can only be fixed by manual intervention.
There is a great article here that explains exactly what you need to look for and how to go about resolving this issue. Using the ADSI Edit tool, you will need to go and compare the “dNSHostName” and “servicePrincipalName” to a known working computer account and make sure that the values match up except for substituting the exact computer name for what value is entered on the System Properties > Full Computer Name screen.
In my particular scenario, it wasn’t actually that particular computer account that was causing the problem. At one point I had a computer named “computerX” that was unjoined from the domain but it must not have removed all of the leftover remnants from the computer account or there was some sort of computer or otherwise network interruption that happened at the time that had caused the database corruption.
Only when I went to try to join another computer to the domain using the same “computerX” computer account name and went to log onto as a user did I get the trust relationship error. At that exact point in time, I didn’t have a lot of time to mess with the issue, so I unjoined the computer from the domain again and simply renamed the computer account to something else, rejoined it to the domain and then was able to log on again.
Eventually today I decided to mess with this issue again when I needed to swap out another computer and tried to name it as “computerX” again and the problem crept back up.
It turns out that on the “servicePrincipalName” entry of one of the old computers, that had been unjoined from the domain and rejoined under a different computer name, still had some entries that were pointing to the old “computerX” computer account that needed to be deleted out. After I did that, I was successfully able to log on again.