Sorry I was traveling today and just got Tim's PM. The solution is indeed a Repair Install as it completely resets activation and makes the installation a clean slate for a new Product key, - whether full retail, factory OEM, and specifically an Upgrade such as you purchased.
But Tim's warning that the install DVD might itself be corrupt is a concern. For example, the pirate seller might have slipped in a BIOS-mod emulation to activate it, although I don't think that would survive a Repair Install, which reinstalls the OS while transferring over files, settings and programs, assuring System File integrity in process.
This is providing you do the Repair Install with a verified install disk whose ISO passes
official HASH check for Win7 Ultimate. using a tool like
Hashtab. You can avoid this by obtaining your install media from a trusted source. I would also test the original install media as having it pass HASH would relieve any fears, although failing HASH doesn't count it out I would be wary of it and study it closer.
I would also use the best lightweight free AV solution Microsoft Security Essentials as it is being updated to detect all activation exploits and other tampering.