I unfortunately have some bad news for you, as the EXACT same problem happened to me and the solution was to uninstall and reinstall everything.
Now did you lose the disc, or give it away, or what? Because if you lost it, you might be able to pay a fee and get Microsoft to replace it if you can provide your proof of purchase. However if you sold it or gave it away, obviously that would not be legal for you to do, because you don't own the game anymore, so the best thing would probably be to try to buy the game used.
I tried very hard to find a different solution to this, as I really didn't want to reinstall myself, but finally ended up having to. I have a hunch when it gives that error message it's finding something wrong with the registry entry, although I could be totally wrong.