Are you trying to register the same product, Parallels 6 old key Parallels 6 new key on the same machine?
When you uninstall the product you need to restart your machine before reinstalling.
I am not sure you can change product keys for same release of Parallels. I would contact customer support, to see if they will exchange the key for you.
The only other area I can think of is "My Account" Have you tried https://www.parallels.com/account/ can register a key to your account that way. But this will not activate it on your machine, it just let the company know who has the key.
Last edited: Aug 16, 2011