When I got my Windows 8 (not 8.1) computer at the end of 2013_12, I started setting it up the first couple of days in 2014_01 (made sure my Windows 7 computer was backed up, all my files backed up, etc). I had a bunch of updates that failed also. Here are the KB numbers of the ones that failed for me:
When I went to Windows 8.1 (boxed copy, about month later), I had no problems with installing updates. When I went to 8.1, I did a NUKE AND PAVE (removed all partitions -- including recovery partition), and built it up from scratch, with the boxed copy of Windows 8.1.
As for Windows 8.1 to Windows 8.1, update 1, I had problems, and I had to download the updates Microsoft Update Catalog, manually install them in a specific order, and all was AOK. When I tried it through the Windows Update interface, in Windows, it would either hang part way through download process, or the update process. It kept changing on different attempts, even after I applied the bare bones, Paragon Backup and Recovery image. I got everything worked out, and wrote the steps down for future reference.
Then M$ re-released Windows 8.1, Update 1 on 2014_04_17, and when I tried to download it then, it was suppose to download around 900MB, and I aborted it, when it was around 3 times the download size was suppose to be. I then downloaded it through Microsoft Update Catalog again, got the around 900MB I expected, and installed successfully, manually.
All users of Windows 8: Remember that per M$, "All future security and nonsecurity updates for Windows RT 8.1, Windows 8.1, and Windows Server 2012 R2 require this update to be installed". They're talking about KB2919355. This means, if you're running any of the above, you'll stop getting updates starting on patch Tuesday next month.
Best of Luck.
Edited by scotty_ncc1701, 27 April 2014 - 01:47 PM.