Windows Server 2008 Restore fails with error 0×80042406

When trying to restore a Windows Server 2008 R2 backup from disk it failed immediately with error 0×80042406
The solution was to hit Shift-F10 and bring up the command prompt, from there type:

diskpart

list all the disks on the machine and find your target disk:

list disk 

Select our destination in this scenario is disk 0 (Yours may be different)

select disk 0

Now we wipe all partition information and filesystem tables on the disk we selected above (destructive!)

clean all

Now try your restore again!