well the Ps2 video is Interlaced .. that is like any normal tv broadcast.. I am not sure it it supports progressive scan as SOME HDTV's do.. so a HDTV is not exactly a solution.

I take it that what your seeing on the screen is:
On a vertical line.. your getting a jagged line..ie appears that the line is serrated..

ok and you have heard or read that it was an interlacing problem.. well the only time interlacing is a problem is in convertiing interlaced video to DVD/VCD/MPG .. and I am sure that is where you got your example image.

This problem you are seeing could be a fault in the TV, or even in your cabeling.. especially if your useing a low grade (cheep) Coaxial cable (read AV Lead) and this lead is passing over the top of the TV (for that matter if the PS2 is sitting immediatly on top of the TV, or just under).. you could be suffering from interferance from the EHT circuit, causing the pseudo ghosting, and or errored Syncronisation problem..

I can't find pictures of jaggies to give you an example for you to compare

Cheers