More information about the error (0xC004F061) here.
According to reports, the same trick/workaround that enabled users to clean install using Windows 7 Upgrade media also works with Windows 8:
Regedit (Win+Q, type
MediaBootInstall from 1 to 0
Go back to the Start Screen and type
Command Prompt and run it as administrator
Run the activation utility, enter the product key, cross your fingers and attempt to activate Windows
Note 1: According to other reports, this method (using the cheap $15/$40 Upgrade key to clean install) does not work with the USB/DVD (ISO) media the Upgrade Assistant allows you to create. Instead you apparently need either the Windows 8 (32/64-bit) DVD version (that contains both Core/Pro) available on MSDN, or possibly the System Builder DVD.
Note 2: If this doesn't work, the double install trick should (as mentioned by Moab).