Uaaah! I had the same error message and after at least 6 failed attempts I reinstalled Win8.1 from scratch. Then the update worked. Later I was having the same error code 0x800F0922 when I tried to install a later patch. Many different attempts didn't help here either.
What was the reason? It happened because I had a dual-boot setup with Linux/Grub2 which the Win-installers cannot handle.
This finally helped me:
http://blog.colbornemmx.com/2014/05/windows-81-update-1-fails-with-error.html
Basically it suggests to restore the initial Win8.1 bootloader (i. e. leave out Grub)
and then do the Windows update. That worked for me!!! Crazy...
Hope that helps some people here with dual-boot. After the installation you can restore the original Grub2 bootloader/partition activation.
Georg