Gracias a Ubuntu FTW ya esta todo solucionado, para quienes tengan este mismo problema solo abran una terminal y peguen la siguiente linea:
udo aptitude install libavcodec52
Fuente:
http://ubuntuftw.blogspot.com/2009/10/error-en-vlc-reproduciendo-xvid-en.html