I would try the following.
1) Media: CMC isn't the best quality media around. I would for sure try something better. Memorex uses up to four different suppliers, check the Media codes link in my sig for deatils (or the media forum).
The 812S prefers burning +R media over -R so I would try some higher quality +R media and bit set it to -ROM (see tools guide in my sig for more info on bit setting).
2) Firmware: Sometimes using a different firmware version will improve compatibility with set top player/PS2/Xbox. You can go back to older firmware's by using the tools found in the guide in my signature.
3) Burn speed: Believe it or not burning at 1x doesn't always produce better quality discs. Try burning at 2x or 4x and see if that helps.