By the sounds of all the complaints seeming to come from OEM installs of windows, I'm betting it might have something to do with it. I have a couple of Dell Alienware R5's I was having issues with, and directly after reinitializing the WinRE partition from scratch, rebooting and having the update fail again, I tried a sfc /scannow. Believe it or not, it found ((something)), and after another reboot, the update actually went though.
obviously, plenty of people have tried plenty of things, and if you followed the list- you likely have already tried this. Or maybe you're like me, and just hate having to babysit a system file checker for a clean install, and thought it futile to try.