This can happen on an imaged machine where the credentials for the domain get improperly cached for the Local System account.
Accessing the creds panel via psexec seems to be the simplest way to see the "SYSTEM" account cached cred's.
1.Use SysInternals PsExec to open a command prompt under the Local System account [http://technet.microsoft.com/en-us/sysinternals/bb897553]:
From an Administrator command prompt: PsExec.exe -i -s cmd.exe
2.Open the Stored User Names and Passwords app under the Local System account:
From the System account command prompt: rundll32.exe keymgr.dll, KRShowKeyMgr
3.You should now see the credentials that are cached under the Local System account. Review the list for rogue suspects, and remove them. For me, this was straightforward. There were two credentials listed: one rogue cred (from my old WHS2011 config I suspect), and a second called virtualapp/didlogical. When I reviewed the credentials on machines that were working, they only had the virtualapp/didlogical credential listed.
I removed the rogue credential, and then gpupdate worked like a charm! Also, running klist -li 0x3e7 now shows a nice healthy set of Kerberos tickets for the Local System account. All is good.
What is most expedient for us finally was to run the psexec command remotely as:
psexec \\computername [or @listofComptuers] -i -d -s rundll32.exe keymgr.dll, KRShowKeyMgr
The -d flag means the remote machine drops the psexec connection as soon as the rundll32 launches, so you can move on with the remote machine, then running the rundll32 rather than cmd saves time not having to type the command on each workstation. This still launches the command at the console on the remote computer, but at least you don't have to go through the motions of launching it on ever box - just removing the entry.