Get a network packet capture of the failed requests and check the Http request header for the kerberos authentication token. If you are expecting a kerberos token and it isn't present, the issue probably isn't your servers.
I'm assuming you are expecting kerberos because of the SPN checklist.
Refer to the following for more information:
https://serverfault.com/a/440050/20701
First, I would confirm that this is occurring from a client where IE shows that the site is in the Trusted Sites zone, and the Trusted Sites zone is configured for "Automatic logon with current username and password."
Next, I would suspect the http authorization header size may exceed the IIS limits. Integrated Kerberos authorization is quite susceptible to this issue due to the IIS limits are actually quite low, and it does not require that many group memberships to bloat the token over the limit.
Each and every request includes the user's Kerberos token in the http authorization header. Because the token is encoded, it is frequently much larger than the actual memory used.
You can increase the values using the following document:
Http.sys registry settings for Windows
http://support.microsoft.com/kb/820129
I would use the following values:
MaxRequestBytes - set to 1048576
MaxFieldLength - set to 65534
Another useful utility DelegConfig. You can drop this in as an application on any web site, and connect to get a nice useful report on how your Kerberos authentication is configured. This would need to be tested as the victim account (or a suitably configured test account taht is exhibiting the symptom in the victim's domain).
http://blogs.iis.net/brian-murphy-booth/archive/2007/03/09/delegconfig-delegation-configuration-reporting-tool.aspx
You may also need to review:
How to use SPNs when you configure Web applications that are hosted on Internet Information Services
http://support.microsoft.com/kb/929650
Specifically:
"In Active Directory, verify that the Account is sensitive and cannot be delegated check box is cleared for users who access the application."
"Verify that all computers that are part of the Kerberos process have consistent name resolution and are connected by Kerberos trust. For example, verify that the computers that are involved in the Kerberos process are in the same forest or are part of a cross-forest Kerberos trust."
"Verify that the token size does not exceed the value that is set for the MaxTokenSize property." (MaxTokenSize should be set to 65535).
Internet Explorer 6 cannot use the Kerberos authentication protocol to connect to a Web site that uses a non-standard port
http://support.microsoft.com/kb/908209
There are also some excellent tips in the following article.
https://blogs.msdn.com/b/friis/archive/2009/12/31/things-to-check-when-kerberos-authentication-fails-using-iis-ie.aspx
In particular, checking that the client is connect to the expected SPN, using NetMon or KerbSpy.
Best Answer
This could be loop back issue, are you trying to access the IIS site from the same machine.
Try accessing the site from different machine in the LAN.