I've followed through multiple threads to find a solution to this error during Microsoft Updates, but I've never found a fix in the forums - it might be there, I just never found it.
Here's what worked for me (only for IE) - I'll include all steps, though I think it was the very last step that actually did the entire fix:
1. Boot into safe mode
2. Click START | RUN | type in net stop WuAuServ
3. Rename the <%windows%>\SoftwareDistribution folder to something like SoftwareDistributionOld
4. Rename the <%windows%>\system32\Catroot2 folder to something like Catroot2Old
5. reboot
6. Launch IE
7. Empty cache
8. Click TOOLS
9. Click MANAGE ADD-ONS
10. Click Windows Genuine Advantage Validation Tool
11. Click the ENABLE button.
12. Click OK
13. restart
I hope this helps someone somewhere.