Fixed by performing these actions:
Net stop Wuauserv
Net stop cryptsvc
Net stop bits
Try running:
ren %systemroot%\System32\Catroot2 Catroot2.old
ren %systemroot%\SoftwareDistribution SoftwareDistribution.old
If above rename commands do not work, manually go to %systemroot% and rename the SoftwareDistribution folder and \System32\Catroot2 folders with a .old or .bak extension. Sometimes you have to re-run the net stop cryptsvc again and immediately perform the rename.
Then, restart the service.
Net start cryptsvc
Net start bits
Net start wuauserv
Your software update should now resolve correctly:
