Comment 2 for bug 163958

This is most likely a problem with a graphics driver.
Please run gstreamer-properties, switch to the video tab and try out the different plugins for "Default output". When you're done, report back your results (what plugins produced good results, what produced bad results). Note that totem uses the gstreamer framework by default (unless you manually installed the totem-xine package). So please try out the different plugins with totem. VLC and others don't use gstreamer, so they won't be affected when you change something in gstreamer-properties.