Figured I'd answer my own question.

The three commands listed above weren't enough. After the second command (the "rd /q /s"), use regedit to remove HKLM\Software\Microsoft\Windows\CurrentVersion\WindowsUpdate, then follow that with the "net start wuauserv". That resolved the 0x80246003 error on multiple Server Core 2012 hosts for us.

Thus, the steps (in our case) were:

1. net stop wuauserv

2. rd /q /s %windir%\softwaredistribution

3. Use regedit to delete HKLM\Software\Microsoft\Windows\CurrentVersion\WindowsUpdate

4. net start wuauserv

This only applies to Server 2012 (or Windows 8, most likely) hosts that had registered with the WSUS host prior to the KB2734608 patch having been applied.