We recently encountered this issue on a remote Windows system connected to AD via VPN. There are two ways to fix it. The simplest is to simply remove/rejoin the computer to the domain.

The other less intrusive way is as follows:

1. Download PsExec (part of sysinternals) from https://docs.microsoft.com/en-us/sysinternals/downloads/psexec
2. From an elevated command prompt run PsExec.exe -i -s cmd.exe (This will open another command window in the Local Machine account context).
3. From that window, run rundll32.exe keymgr.dll, KRShowKeyMgr (That will open a gui with a list of cached credentials).
4. In that gui, delete any credentials that match your PDC.
5. Logoff and log back in, run gpupdate.exe and it should immediately start working.

Credit to this serverfault article.