Try this unlikely fix. It seems to do the trick, although it makes no sense. I had the problem on one of my laptops. Tried all the tricks but this worked.
Right click the start menu and selct Command Prompt (Admin)
run this sfc /scannow
It will take a while, then try the update again