Hoy me paso que no podía ver una de mis series favoritas «Californication» en mi querido VLC, pero gracias a Ubuntu FTW ya esta todo solucionado, para quienes tengan este mismo problema solo abran una terminal y peguen la siguiente linea:
sudo aptitude install libavcodec52
Fuente: http://ubuntuftw.blogspot.com/2009/10/error-en-vlc-reproduciendo-xvid-en.html