Consegui resolver este problema por -
sudo add-apt-repository ppa:mc3man/gstffmpeg-keep
sudo apt-get update
sudo apt-get install gstreamer0.10-ffmpeg
A última biblioteca de repositórios "ffmpeg" não possui os codecs necessários ao meu sistema e eu tive que instalar o gstreamer0.10-ffmpeg (não no repositório) do ppa.