Error: We couldn’t complete the updates, Undoing changes. Don’t turn off your computer.

I'm happy to report that after everything, the "in-place repair," which is basically a non-destructive reinstall, finally did the trick. 

@RonSarid, what was the procedure you followed to do the in-place repair?  Did you have to do anything after the repair to get your system back to a fully functional state, other than catching up with any outstanding Windows updates?  I was informed by Microsoft that I would have to re-install my applications.  Searching the Internet does not provide consistent/definitive answers.

Hello NH905,

If you can do an "in-place repair," then you won't have to reinstall anything really.   I was told that this can only be done with Windows 8.1 media (either a physical disc or one made from a downloaded .iso).   The procedure is simple:  Once you have the disc in your hands, pop it into your computer and start the setup.exe.   This will pop-up a screen giving you 3 options for a Windows install.   The first option is "keep windows settings, personal files, and apps."   This is the option I chose that preserved my installed software.   Please note that some 3rd party desktop apps (from the store) might not be preserved, however your installed software (office, adobe, etc...) will be fine and unaffected.  I was most worried about Outlook and Photoshop (and a number of smaller utilities) but all worked fine after the repair.

The one tricky part of this (besides getting the media disc), is matching the correct product key.  If you are like me, you will have a valid Windows 8 product key, but not a Windows 8.1 product key because you updated to 8.1 via the store.   Doing an "in-place repair" requires a product key to match the media disc you are using for the repair.  My windows 8 key did not work.   The MS L2 Engineer entered a generic 8.1 code for me to continue the repair and advised me that I will need to later change this to my own key for activation at the end of the process.  For what it's worth, a quick google search for "8.1 in place repair" turned up a number of websites that had complete instructions on how to do this and included generic 8.1 keys to get you started.   Hope that helps!

Very nice, a non-destructive solution... worked for me.   I found my media and key, and was fixed and fully updated within an hour and a half.

THANK YOU

Error: We couldn’t complete the updates, Undoing changes. Don’t turn off your computer.         I get this code on my screen:                                         0xc1900101 and 0x40017

Getting super annoyed by this.  Every time I try to update and this happens I can't use my laptop for an hour while this is going on!

error code KB2966804