FIX: The security database on the server does not have a computer account for this workstation trust relationship

Here are the steps I take to fix this issue:

1. Open up Active Directory Users & Computers pointed to the domain the computer account resides in
2. From the View menu, make sure that Advanced Features is checked
3. Navigate to the part of your organizational unit OU structure where the computer account for this server resides
4. Open the Properties for the computer object
5. Choose the “Attribute Editor” tab on the Properties dialog box
6. Check the Attributes dNSHostName & servicePrincipalName – anywhere that a fully qualified hostname is specified (e.g. myserver.mydomainname.com), make sure that the entry matches the hostname you have configured when you go here on your server: Start -> Computer -> Right-Click, Properties -> Change Settings (under “Computer name, domain… settings”) -> Full Computer Name
7. Also check that particular client/machine facing issue is disable account in Active Directory Users & Computers-Computers-Computer object.
8. If it is disabled, right click and just enable this account.

As an example, for W2K8 R2 server whose Full Computer Name is 'abc1.domainname.com”, these attribute/value pairs should be in Active Directory:
dNSHostName:
abc1.domainname.com
servicePrincipalName:
HOST/ABC1
HOST/abc1.domainname.com
RestrictedKrbHost/ABC1
RestrictedKrbHost/abc1.domainname.com
TERMSRV/ABC1
TERMSRV/abc1.domainname.com

If you find that any of these entries is incorrect, go ahead and fix them; once they all align correctly try logging in again.  After you make any changes, please remember that it may take up to a few minutes for changes to replicate between the Active Directory domain controllers.