Service account changed for SQL? Does it have the ability to register / deregister SPN's in AD? SPN's configured and right? Rebooted domain controllers recently?

That error is usually related to SQL trying to contact AD for a kerberos ticket and failing.