What OS was originally installed on the HP? You are entitled to reinstall that as often as you want for the life of the machine.
Clean Reinstall - Factory OEM Windows 7 Vista ISO download
If it wasn't Windows 7 then you were right to buy a copy to install, likely Upgrade version is all that's needed. In activating it the reason 90% of activations fail is typing a wrong character since several look alike. Triple check the key against what you type using a magnifying glass if necessary.
Finally no retailer can get away with selling you non-genuine WIndows as it is both a crime and will be pursued by MS. In fact if you cooperate with an investigation by MS Customer Service they often will reward you with a free copy. So I would call them if the key cannot be made to work, and the merchant will absolve himself of a crime.