Some of the procedures necessary for reinstalling some types of software are shrouded in mystery. As suggested, calling Microsoft is probably the best bet.
Was this an upgrade version of Windows 7, the one where you originally needed to have a prior OS installed? Microsoft should have a reference for your key and the computer combination, so hopefully they will just allow you to reactivate. You may have to go through the numbers game if you call, but that is not a big deal.
Let us know how it goes, and if this is a reinstall of an Update Version of Windows 7.
Also, make sure you are reading the key correctly, so characters do look like others.