I've had a couple of DVD players do the same thing. The first was a first-generation Sony. After much searching I found a site that gave me the key-combinations to enter the service and maintenence menus. I ran the auto-calibration utility and that fixed it right up. I later gave that player to Goodwill since it became obsolete regarding the ability to play most burned discs, MP3 discs, and such features as progressive scan DVD.
My second player was a Panasonic DVD-S35. I like this player very much. Matter of fact I bought another one for the bedroom. But it turns out there is a flaw in the retraction mechanism that can rear its ugly head and can cause discs to not get aligned properly for playback. Wish I would have known this at the time I bought the second S35. Like most lower range electronics this player is not worth the cost of having it fixed. For now I have the bedroom S35 in the main system and a cheapy $50 CC special in the bedroom until I can convince myself it's alright to buy that Denon 3910 or like-quality universal player.
So, if the cleaning disc doesn't work see if you can find the diag and maintenence utility codes on the internet. If the player is not under warranty it may be more cost-effective to buy a new player than get the current one fixed.
