I think I know what happened! You put in your key during the initial installation, and it crashed while you were online through the USB tether. This means that the key was activated at this point, before any chipset/network drivers had been installed. This will mean Microsoft's activation servers will have recorded some slightly different hardware information. It will appear to them as if it is a completely separate PC.
To get around this, you can activate using your phone. Open slui 4, select your country, and when it comes to the help screen explain that you have re-installed on the same PC due to a failed setup. Most of the time retail keys will be approved.
If this doesn't work, return to the shop with your receipt. As the key is a retail key and has only ever been used on one PC it should not be blocked. They need to either resolve the issue with their distributor or provide you with a working key.