On WS2012R2 I only had to uninstall KB2938066 from Programs and Features and reboot. No changes made client-side. Clients remained at Core/Aux of 7.6.7600.320, but started working again.
In troubleshooting clients I tried wiping out WUagent entirely and re-registering DLLs as per http://support.microsoft.com/kb/971058 but it made no difference. Strongly hints at the root cause being server-side.