Old thread, but this was great advice. I ran into the same issue but with different error codes (0x080070057, 0x80070490). I did all your suggestions as well as the following which I gleaned from elsewhere on the interweb:
1. Set bios boot order to DVD then HD.
2. Leaving the external storage where the backup is located disconnected. Connect only when it starts to scan for backup media (might have to refresh or select "different backup" and then refresh).
3. Restore to drive of same size or greater. This is actually quite a peave for me - i wish i knew how to restore to a drive even slightly smaller. I had a 100GB system partition that i was restoring, but the physical disk was 300GB. I tried to restore to a 160GB disk using the entire space but it wouldn't let me. I had to get out an old 320GB that has been gathering dust.