Microsoft article ME828246
helped me solve the problem. The service account was not a member of the local administrators group.
The cause of this issue may be the SQL Server service account running as a domain user who does not have requisite permissions to register SPNs. See the link to "Veritas Support Document ID: 277728" for additional information about this event.
This is not really an error, accourding to Microsoft. They say it is an informational message. See ME303411
From a newsgroup post: "No reason to worry. On startup SQL Server tries to write to the Active
Directory, and register the SPN (ServicePrincipalName or service name. The warning indicates that it could not contact the Domain Controller to accomplish this. Error 1355 is: The specified domain either does not exist or could not be contacted. This should not be a problem as SQL does not rely on the Active Directory and I haven't seen this error cause any problems with connectivity to the server.
As per Microsoft: When SQL Server starts on a computer that is running Microsoft SQL Server 2000, the SQL Server program always attempts to register the virtual server in the Active Directory. You may see the 1355 event the event log. This message is not an error message. This text is only a warning that SQL Server was not able to register a Service Principal Name (SPN), which indicates that the security mechanism that will be used is Microsoft Windows NT Challenge\Response (NTLM) authentication instead of Kerberos.
The message usually appears because the SQL Server service account is running as a domain user who does not have requisite permissions to register SPNs. Additionally, the error may be related to the fact that the server is a clustered or fail-over virtual server, which are not currently supported by Active Directory.
Microsoft has confirmed this to be a problem in SQL Server 2000.