Going through the Microsoft KnowledgeBase updates, I saw this one:
An SPN for the SQL Server Browser service is required when you establish a connection to a named instance of SQL Server 2005 Analysis Services or of SQL Server 2005
The situation occurs when the client is connecting to a Named Instance of SQL Server 2005 Analysis Services or SQL Server 2005 Database Engine and SSPI=Kerberos is used in the connection string. If this isn't specified, Kerberos is first attempted, but then the security protocol is dropped down to NTLM or NT_ANONYMOUS is used instead (but just for the connection to the SQL Server Browser service). However, specifying Kerberos forces the connection to stick with it and if the SPN doesn't exist, the connection to the browser service to look up the port fails.