According to a newsgroup post the following steps will clear the error:
dsacls "CN=AdminSDHolder, CN=System, DC=microsoft, DC=com" /g "NETWORK SERVICE:WS, Validated write to service principal name"
(replace microsoft, com with your AD domain name)
Wait an hour, then restart the WinRM service.
Here's how I resolved this error. This was specifically on SBS 2008 servers but may work for other OS's.
1. From an administrative command-line, run setspn -R -S <SERVERNAME>
2. Open adsiedit.msc. Connect to Default Naming Context. Expand domain. Expand Domain Controllers OU. Select Properties of domain controller object. Select Security tab. Click Advanced button. Click Add button. Type "network" and click OK button. Select "NETWORK SERVICE" name and click OK button. Change "Apply to" to "This object only". Scroll to bottom of Permissions list and select Allow checkbox for "Validated write to service principal name". Click OK button. Click OK button. Click OK button.
3. Restart WinRM service.
I used the suggestions on TD348559
to fix this problem on Windows 2008 R2.