I have the same problem and it is driving me insane. I am running an inspiron8k with geforce2go 32mb. I am running debian sid. This problem is just as you explained. I fixed the problem by downgrading to 3123 and compiling from source, however the lastest update of deian's xsever-xf86 package recreated the problem and Im pissed off! I have found one solution. Start a different movie in mplayer and go to fullscreen and you should have the black lines. Now open the video you want and it should work in fullscreen no prob. This doesnt make since to me as the problem doesnt seem to be repeatable. If you cycle between fullscreen and normal about 15 it will eventually work - go figure...
I hope someone has a better solution since with the latest xserver upgrade 3123 is no longer working.