Are you running your PS2 through a VCR or other pass-through device? I remember that happening when my family used to run our DVD player through our VCR. Plugging it directly into the TV could solve the problem.

If that's not it, check the cables.