Telepítsd a gstreamer-properties csomagot, melyet majd Multimédiarendszer-választó néven találsz meg vagy beírod a parancsként a csomag nevét. Ha a gstreamer csomagok végzik a kódolást akkor érdemes ebben (is) állítgatni: gl, X11, xv, stb.. Lehetséges, hogy segít. Igazából a beállításokat a Totem lejátszóban tudod leellenőrizni, mert az a Gstreamer-t használja (a többi lejátszónak nem néztem igazából utána).
Vagy vedd fel ezt a PPA-t
https://launchpad.net/~jon-severinsson/+archive/ffmpeg
és telepítsd az újabb ffmpeg csomagokat belőle, akor a VLC és az SMPlayer is megjavulhat ... ha ez a gond, de nem tudom, melyik rendszert használod, úgy látom a Quantal-tól felfelé van benne a "legújabb", a PPA-s majdnem:
http://packages.ubuntu.com/search?suite=default§ion=all&arch=any&searchon=names&keywords=ffmpeg