Como vlc tem decodificadores embutidos, eu recomendaria instalá-lo em vez de instalar manualmente os plug-ins ausentes para Totem (o media player padrão).
de um terminal: sudo apt-get install vlc
Usando o Centro de Software, basta pesquisar por vlc e clicar em instalar