New
#11
There is no reason to buy a new copy of Ultimate since you own Home Premium which came with the laptop and has approx $100 value you'd be wasting by not using it. Unless you actually need Ultimate for one of it's few extra expensive features, you can use Ultimate elsewhere. Compare Windows 7 Editions - Windows 7 Forums
To reinstall the licensed version to the new HD follow the steps in Clean Reinstall - Factory OEM Windows 7. Everything you need including the latest official Home Premium installer is there to get and keep a perfect install.