First you don't have to uninstall the product key. If you are using a legit copy of Windows it will work. A great example is that I have a legit copy of Windows 7 Professional 64bit. I have installed that same copy on different computer builds of mine about 6 times. Every time I upgrade my computer or change the motherboard, I just have to call the Microsoft 800 support line and use the automated system to reset my key. Once you have used a legal key I think about 10 times you have to speak to a Microsoft Rep and they will reset the 10 time limit. If your key says it is illegal and assuming you have a legal key, all you have to do is call Microsoft with that key and do the activation.
This is what you should do every time you Reinstall windows.
I think the real steps to do this is
2.) Control Panel
4.) Somewhere on that screen should say Activate my copy of Windows or something similar.
5.) When activating it should give some options to do the internet or call the Microsoft number to complete the activation.
Also i would try that activation again. Try to Disable the key Shut down Windows and Reboot with it deactivated. Then activate it again. Your background should change. It sounds like all you need to do is change the Background. but if Windows has locked you out the best thing you can try to do is reactivate it.
NOTE: (for others reading this not the OP) The above steps will work if you are using a legal bought copy of windows. With a Legit copy of windows you can personally install it on your computer as many times as you want even if you upgrade the computer. You just have to activate it each time.