Duplicate SPNs causing NTLM fallback

The NTLM authentication fallback is a symptom. The real problem is why is Kerberos failing.

This sounds like a classic case of the impersonation level that is obtained is insufficient to perform the requested activity. Using delegation with Kerberos, if the machine or process that is impersonating does not have an "Impersonation" token, but instead a lower token such as "Identity", requesting Kerberos authentication to access resources on using another identity will fail.

There are four types of impersonation tokens:

Anonymous
Identity
Impersonation
Delegation

"Impersonation" allows impersonation to access resources on the same machine where the process performing the impersonation is located. In cases where the process performing the impersonation is accessing resources on a different computer than where the impersonation is being performed, a "Delegation" token is required. This typically requires the TCB privilege (Act as part of the operating system).

TokenImpersonationLevel Enumeration
http://msdn.microsoft.com/en-us/library/system.security.principal.tokenimpersonationlevel%28v=vs.80%29.aspx

Note that DCOM in Windows XP/Server 2003 the Default Impersonation Level is "Identity". This means the process may not be able access resources while impersonating another identity. You may want to experiment with the machine-wide or process level security configuration to find what works. You may find that you need to enable encryption to connect to some resources. Configuring one service the same as the other may not be an apples - apples comparison.

Connecting Between Different Operating Systems
http://msdn.microsoft.com/en-us/library/aa389284%28v=vs.85%29.aspx

Setting System-Wide Security Using DCOMCNFG
http://msdn.microsoft.com/en-us/library/ms680051%28v=vs.85%29.aspx

Setting the Default Process Security Level Using C++
http://msdn.microsoft.com/en-us/library/aa393617%28v=vs.85%29.aspx

A Service Principal Name is a concept from Kerberos. It's an identifier for a particular service offered by a particular host within an authentication domain. The common form for SPNs is service class/fqdn@REALM (e.g. IMAP/mail.example.com@EXAMPLE.COM). There are also User Principal Names which identify users, in form of user@REALM (or user1/user2@REALM, which identifies a speaks-for relationship). The service class can loosely be thought of as the protocol for the service. The list of service classes that are built-in to Windows are listed in this article from Microsoft.

Every SPN must be registered in the REALM's Key Distribution Center (KDC) and issued a service key. The setspn.exe utility which is available in \Support\Tools folder on the Windows install media or as a Resource Kit download, manipulates assignments of SPNs to computer or other accounts in the AD.

When a user accesses a service that uses Kerberos for authentication (a "Kerberized" service) they present an encrypted ticket obtained from KDC (in a Windows environment an Active Directory Domain Controller). The ticket is encrypted with the service key. By decrypting the ticket the service proves it possesses the key for the given SPN. Services running on Windows hosts use the key associated with AD computer account, but to be compliant with the Kerberos protocol SPNs must be added to the Active Directory for each kerberized service running on the host — except those built-in SPNs mentioned above. In the Active Directory the SPNs are stored in the servicePrincipalName attribute of the host's computer object.

For more information, see: Microsoft TechNet article on SPN, Ken Hornstein's Kerberos FAQ