Diria que a mi no me hizo falta, pero aun asi te los puedes bajar de la pagina del mplayer (http://www.mplayerhq.hu/homepage/design7/dload.html) , asi de memoria creo que los has de colocar en /usr/local/lib/codecs/.
Si aun asi no funciona el vlc de windows lleva los codecs compilados y no usa los del sistema, asi que con un poco de suerte el que esta en los repositorios de ubuntu tambien.
