Mostly when I have issues logging on to a server, it's due to DNS problems. Sometimes the secure channel is messed up, but the last time it was actually quit simple: there was no SPN for the server in Active Directory.
The error: "The security database on the server does not have a computer account for this workstation trust relationship."
On a windows 2008 server the setspn command is built in. When I exectued "setspn -l servername" it returned no spn's for the server. Simply running "setspn -r servername" fixed the whole thing, immideately allowing me to log on again.