Well, without looking really close at it I would suspect that the artifacting is the result of the image being scaled up to match the max vertical area of your LCD. Unless your screen is an exact multiple of 640x480 (unlikely) then as I said before the choices are black bars all around, or scaling. Unfortunately you probably don't have a choice for black bars and it looks like the scaling left evidence.
This, BTW, its exactly why I still use old CRTs. From what I've seen and heard getting any flat panel display that doesn't have some inexcusably stupid problem (like yours) is impossible. While I'm sure PS3 games going through HDMI look great, I *need* to be able to play low res consoles, laserdiscs, VHS and all that, and I'm sure I'd hate any set I bought.