I'm coming to the conclusion that all this digital processing malarkey really does not lend itself well to Sky transmissions, or indeed anything with compression artefacts. I'm returning a PD30 this week and getting a refund; it had a number of problems but most relevant to you is that the Sky+ pictures were grainy and skin textures unnatural. The quality seemed to be at the whim of the set - once scene could look great, the next awful.
I would not expect that a new SCART cable will make much difference. Indeed, a better quality cable I tried made the problems you mention worse. Swtiching the Sky box between RGP and PAL helped (PAL was better).
I'm now going to be treating my old Toshiba 28" with the love and care it deserves. God forbid it goes wrong - or doesn't power up now.