Ei, rafael###, tente resolver o problema instalando outros pacotes, veja abaixo todos que meu sistema dispõe para execução de arquivos multimídia, áudio e vídeo:
totem-xine libxvidcore4 lame sox ffmpeg mjpegtools vorbis-tools mpg321 libxine-main1
gstreamer0.10-ffmpeg gstreamer0.10-gl gstreamer0.10-plugins-base gstreamer0.10-plugins-good
gstreamer0.10-plugins-bad gstreamer0.10-plugins-bad-multiverse gstreamer0.10-plugins-ugly
gstreamer0.10-plugins-ugly-multiverse libxine-extracodecs gstreamer0.10-fluendo-mp3
gstreamer0.10-fluendo-mpegdemux gstreamer0.10-gnonlin gstreamer0.10-sdl faac faad alsa-oss
w32codecs libdvdcss2 libdvdread3 libdvdnav4 libxvidcore4 libdvdplay0 gstreamer0.10-pitfdll
Se ainda assim você estiver com problemas, instale outro reprodutor multimídia ou informe qual versão do Ubuntu está utilizando, principalmente se for para computador/plataforma 64 bits.