Reinstalling a new legitimate version is the best way forward. If the Product Key printed on the CoA on the case is not the right one, the system must have been reinstalled before. Does the system ask for the key when you try to reinstall? If so, the key on the case might be the right one for the od system but simply doesn't match the CD. If you can find another CD which m,ight actually be yours, it may work better.
If the system will work long enough to load Windows, MagicalJellyBeanFinder will find and decrypt the key from within the installation. Google for a download.