Can I run Windows 7 over Vista or format and clean install 7?

I have Toshiba Satellite Laptop with Vista Home Premium 32 Bit SP2 OS. A few days ago I installed a new 320GB Hard Drive, Booted it with the Recovery Disc, entered the Product Key which failed to activate Windows. Called Microsoft and found they don't sell the Product Keys any longer. I Need to get rid of Vista and move up to the Windows 7 Home Premium 32 Bit SP1 OS. Can I run Windows 7 Home Premium 32 Bit SP1 OS over the top of Windows Vista Home Premium 32 Bit SP2 OS? Also, can I format the Disc on the Toshiba and run a OEM Clean Install with Windows 7 Home Premium 32 Bit SP1 OS? I think it is better to have a plan A and a plan B, just in case.