|If the key worked previously with that cd and you're entering its letters and numbers correctly then it should work.|
I had that problem once. I knew I was entering a valid key but kept getting that message. It turned out the hard drive had died between the time 98 setup had last accessed the drive and when I input the key. Setup couldn't verify the key because the verification procedure had been loaded to the hard drive which was now dead.
But your drive isn't dead so I'm thinking maybe the verification is loading to a bad spot and can't be done.
Or maybe the cd or cdrom is going bad.
First thing you might try is doing a surface scan with scandisk prior to installing 98. Maybe you can do that from your current set up or from a bootdisk. If it finds any bad spots it'll mark them and they won't be used.
Another thing you could try is copying all the files from the WIN98 directory on the 98 cd into a similarly named folder on the hard drive. Then run setup from there and not even use the cd for installing.
Check my #13 here:
You can extract your current key from the system running now and see if it's the same as you're trying to use now.
If you wanted to get rid of 98 altogether you could repartition the drive thereby removing both the existing 98 and linux and then reinstall just linux.
Ubuntu Cheeta, Ubuntu !