Which video player are you using?
Maybe try switching to vlc or mplayer?
Do you have hardware acceleration? (type 'glxinfo | grep rendering'), if not you may have trouble with full screen playback. In vlc you can try a different video output module
if you start it from the command line using 'vlc -vout <module>' (type 'vlc -l' for a full list of modules) In mplayer you can select a different driver in Preferences->Video