ONE SOLUTION: (Or at least what worked for us.) We had a workstation with the exact same error message. Rejoining the domain did not correct the issue. The only thing which worked was to use an entirely different computer name, which was not our preferred solution. After much searching (including finding this page) and gnashing of teeth I finally found the problem in our domain.
There was a duplicate SPN (Service Principal Name) registered on another computer account. For some reason setspn -X was NOT finding the duplicate entries. Instead I ran setspn -Q */hostname* where hostname was name of the computer. (not the FQDN)
This turned up another computer account with a duplicate SPN:
C:\Users\tblackerby>setspn -Q */hostname1*
Checking domain DC=mydomain,DC=edu
CN=EDBB9F19DB3E435,OU=Other Computer Objects,DC=mydomain,DC=edu
HOST/EDBB9F19DB3E435
HOST/hostname1.mydomain.edu
CN=hostname1,OU=Lab Workstations,OU=Workstations,DC=mydomain,DC=edu
TERMSRV/hostname1.mydomain.edu
RestrictedKrbHost/hostname1.mydomain.edu
HOST/hostname1.mydomain.edu
HOST/hostname1
RestrictedKrbHost/hostname1
TERMSRV/hostname1
Existing SPN found!
I used ADSIEdit to remove the SPN off of the conflicting account, waited for replication, and was finally able to login to hostname1 without the error!
To verify I can recreate the problem by putting the duplicate SPN back on the other computer account, which immediately causes the error again.