Couple things you can do.
First, try going composite instead of S-Video. Believe it or not, sometimes that helps.
Second, try adjusting your set. Turn down sharpness, brightness, etc. Sharpness in particular is bad on SD-resolution programming.
Basically your new TV is just making it easier to see the flaws in the SD stuff.