Stop the Windows Update service.
net stop wuauserv
Delete the Windows Update cache directory
Remove-Item -Recurse -Force C:\Windows\SoftwareDistribution
Restart the computer. (On one machine it required several restarts to actually get everything deleted from this directory, so keep trying if necessary.)
Run Windows Update manually again. It will fail almost instantly and offer to run a diagnostic tool. Download the tool and allow it to run.
The tool will find and fix some problems. At this point, run Windows Update manually again. Windows Update should work this time.