PLEASE NOTE: Now that Microsoft has released their officially supported fix I am no longer providing the download for the recovery drive. If you wish to keep a small recovery drive then repair your system using the instructions from Microsoft, then follow “Option 1” to create a new small boot drive.
Microsoft have now released the Full Recovery Image for WinRT (3.7GB download). You can get it here http://www.microsoft.com/surface/en-us/support/warranty-service-and-recovery/surface-rt-startup-error-0xc000000d?lc=1033
It uses the same steps to complete the upgrade with the last part being to recreate the full recovery volume. Some news sites are saying the MS image will revert you to 8.0, it does not. It will complete the 8.1 upgrade and then the extra steps are to recreate the on-device recovery volume with the 8.0 image which only applies if you rollback sometime in the future.
COMMENT: I’ve also received confirmation that my approach works on a Japanese and other non-English language WindowsRT devices, which is good news as that’s not a test I could have done, and hadn’t even considered tbh. Also, While I refer to “Surface” because that’s what I have. these steps will also apply to any WindowsRT tablet device.
So something has gone horribly, horribly wrong. You do of course have the USB key you created shortly after setting up your Surface, don’t you?
Don’t worry, even though I do this sort of thing for a living, even I hadn’t created a recovery USB Key. Luckily for me though (or unlucky depending on how you look at these things), I have two Surface tablets. After the Win8.1 upgrade, one worked fine, the other suffered the Boot Configuration failure – https://kickthatcomputer.wordpress.com/2013/10/19/windows-rt-8-1-upgrade-fails-with-boot-configuration-error/
So here I’m going to describe the ways I’ve found to create your recovery USB key. Make sure to read to the end because you will most likely also need to recover your BitLocker encryption key as well (it’s like the complications never end!)