I am currently sitting with the same issue on a SQL 2008 R2 server running on a Server 2003 R2 SP2 OS, I had to install the setspn.exe from http://www.microsoft.com/en-us/download/details.aspx?id=4461
I got the server registered by running setspn -R MYSERVERNAME in command prompt.
I will let you know if this resolved it after the server gets restarted later.