Trust relationship between machine and AD failed

I've run into this problem only a couple of times and Technet has quite a few possible solutions - the one that worked for me was using Netdom.