I had this exact same problem.
You need the new version of windows update. The problem is, the patch notes for the updates you need don't actually tell you that they update windows update.
You need KB3173424 first, then install KB3172614. You should disconnect your computer from the network and restart before installing these after downloading.
I don't actually know if disconnecting your computer from the network to prevent windows update launching in the backround is necessary, but it worked for me. Similarly, I don't know if the updates must be installed in that order, or even if you need both of them. I just know it finally made the update process work. Hurray.