Most recently, a client had this occur for the oddest reason - it seems that one of the Front-end servers had run out of space and after a short time, completely locked out one of the sites. Cleanup and reboot did not fix the problem - the solution ended up doing a DNS Flush - after that, it appeared to clear the problem.
That said, I've seen other cases where this has happened due to flaky DNS, load balancers, etc.
So a quick fix is to 1) Follow the same rules as we use for Kerberos authentication using the SetSPN command (Service Principal Name). For an overview on this, see here:
For specific detail on the command and syntax, see here:
Another quick fix is to use the Hosts file found on each of the servers (c:\windows\system32\drivers\etc folder). Edit this file with Notepad and simply add all of the servers and IP addresses to the end of the file. For example, for domain xxx.com:
The downside to this of course, is that any changes mean manual changes on all servers.