Some additional information
I've been experiencing the same problem with my LCD monitor (Samsung 152T). I've tried the suggestion of starting another video first and that seems to work. BUT, the suggestion about changing my VertRefresh to 60 did not work.
I do have some additional information that might be helpful:
1. My monitor has dual input (DVI and analog). This problem only occurs when I use the DVI connector. Using the analog VGA works perfectly fine.
2. puterguy said in his last post that using x11 vs. xv drivers has no effect. For me, though, this is not the case. If I run mplayer with x11 output, eg.
mplayer -vo x11 -zoom -dvd 1
and then switch the fullscreen, I do not get the "jaggies".
My config is almost identical to puterguy's.
Hope this information will be useful to somebody.