Problem:
When installing a Windows 8 upgrade on a Vista laptop, and trying to use the in-place upgrade option, the installation would fail at 10% complete. When I instead used the DVD to perform a fresh installation, and entered my valid serial number, I got the message "We couldn't verify the product key. Please check your installation media."
Solution:
It turned out that the installation files were corrupted during download. Downloading the files again and burning a new DVD from the resulting ISO let me proceed without further trouble.
Protip: During the initial installation from DVD, pressing Shift+f10 brings up a DOS command box. If you have cleverly copied and pasted your key into a plain text file (say, 'keyfile.txt') on a memory stick, you can then change directory to the stick (try 'cd d:' and replace the 'd' with other letters until you find the stick), enter 'type keyfile.txt' and the number will appear. Highlight it with the mouse, hit enter, then click back on the installation window and paste. This ensures that the key is copied correctly with no typos.