Hi. You should make extra sure (though you likely have already) that the serial number is entered correctly. It's easy to mistake a zero for the letter o or the number 1 for the small letter l, etc.
Click on the Apple Menu in the top Left of your MP's screen, and select "About This Mac." Then double-click on the Serial Number, and copy it by right clicking or by pressing "Command + C" and then paste it into the form. (This ensures no errors are made in entering the serial number.)
If it lists a real-looking serial number try typing that into the website to verify:
http://checkcoverage.apple.com. (Sounds like you already did this, but....)
If you still need help, contact Apple Support. (If you had repairs done recently whether the motherboard was replaced, that might possibly explain it, too.)
Good luck!
--JDee