Yeah, unfortunately it's a pretty messed up situation, particularly if you actually like to upgrade or customize your PC (Vista's own licensing can have issues with that unfortunately, but not with HDD's as far as I know). But yes, the HDD needs to be "Tattoo'd" as they call it. I've worked at Best Buy, Circuit City and CompUSA as a tech in the past, all of which are or were certified HP service centers and that's how I knew about it because I've had to do it. As long as the computer is still under warranty then you can use HP's locator here
to find a service center near you and they should perform the work for free as long as the old HDD is provided as proof of failure. I'm not sure if they'll let you use the other drive you had or if they'll have to order one, but they should have the disc needed to make the install work on hand (HP sends out a binder full of discs and sends updated discs for newer models to their service centers regularly).
Hopefully these OEM's like HP and others will learn that when most people buy a PC they don't expect to get a system full of proprietary hardware and software, if they did then they'd probably buy a Mac instead.