Last night I was able to update Win 8.1 after 2 months trying uncountable number of times. My problem was (WAS !) error 0xC1900101-0x40019 after blank screen and restauring Win 8.
I tried all tips from here, HP and others web sites, fresh install and update, no fresh and update, and so...
I have a HP ENVY 15-j011dx, it has a Intel 4000 video card and I can say that the my problem was not with Microsoft but HP Video driver.
My Win 8 had Intel High-Definition (HD) Graphics Driver 2013-04-15 , Version 220.127.116.1171 from HP recovery USB bought from HP and it is the same version that is on HP website now.
For short, the trick was to uninstall Intel Graphic Drive listed on Program and Features before uninstall the video driver on Device Manager. But TAKE CARE !!!! You must be prepared, you MUST have the new driver for Win 8.1 ready to install just after the upgrade because Win 8.1 will bring back the Version 18.104.22.16871 and you MAY have a back screen AFTER the upgrade and if so, you will have to boot in SAFE MODE to install the new driver. Let me explain:
1. Download the video driver pack for Windows 8.1 (from HP in my case version 10.18.10.3304) and save it on your desktop to be easy and quick to find later, this is the MOST INPORTANT STEP !!! If you don't do it don't try to upgrade with this method or you may have to do a fresh install !!!!!!! If you can PIN it on START and let it on the first screen, easy to find, will be better.
2. Uninstall Intel Graphic Drive on Program and Features, this is NEW, I didn't read it, is not cited anywhere to do this, and THIS IS THE TRICK .
3. Uninstall the video driver deleting the driver in Device Manager. It should show a Microsoft Video Driver WDM ( something like that) NOT the Intel 4000 driver. Reboot the system a couple of times to make shure that Windows 8 will not bring back the Intel 4000 driver.
4. Upgrade to Windows 8.1 from the store. ( I could update even without downloading again, I had already the BT folder).
5. JUST AFTER the first time you see the Start screen on Windows 8.1 quickly install the video driver for Windows 8.1, I mean QUICKLY !!!!!
6. When I upgrade it I didn't know that the Windows 8.1 will bring back the bad video driver. I start Windows 8.1 but after a minute or two I GOT a black screen with Windows 8.1. As I had it under control, I knew was the video driver, I boot in SAFE MODE and install the video driver, reboot and did all updates from Microsoft and HP (the they choose) without problem.
This might work with other versions of video driver or the concept may work with other brand of video card, It work for me and make sense.