Our users came across the following error when they were trying to login to their My Site (http://mysite/):
We had recently had to restore the My Site from a backup and it appears the restore process had changed the authentication type the extended website http://mysite/ was using from Kerberos to NTLM. We have another version of the site published as http://mysite.domain.com/ which was still set to Kerberos hence the authentication error.
The fix was to go into Central Admin - Manage Web Application (My Site) and then select Authentication Providers. I selected the offending Intranet zone and changed it back to Negotiate (Kerberos) so it matched the other Custom zone:
After an IISRESET, the error stopped appearing.