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
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.