Is it horrible gashes/scratching that's causing the problem? If so, the only solution would be polishing them away somehow, and it sounds like you already tried that. Your only other option is getting another copy and trashing the bad disc.
Be sure to check the terms of the warranty in the instruction manual. I'm pretty sure it's just 60/90-day for replacement, but you never know.
Also, make sure the bottom isn't just covered with something opaque. Use a 100% cotton T-shirt and a mixture of 50% rubbing alcohol (isopropyl) and 50% water to gently clean it. That's also a good solution for cleaning most screens and lenses.
I hear you can use toothpaste to polish CDs, but with all the different types of toothpaste out there, I wouldn't trust this bit of advice even if it were true.
Instead, you might take it down to a game shop and ask them what they think. They might have a scratch-removal machine that grinds away some of the plastic to lighten deeper gashes and scratches, then polish the disc. Even if they charge you a small fee, it'll still be a lot cheaper than replacement.
