Sempre que aparece alguém tendo problema com execução de arquivos de mídia (falta de codec 99% das vezes) a galera sugere instalar o VLC antes de qualquer coisa.
Eu sei das qualidades desse player, já usei muito principalmente no Windows (com seu inferno de codec packs), sei que é mais "fácil" indicá-lo por seus codecs internos.
Mas, para mim ao menos, fica parecendo algo desvirtuado, visto que foi implementado no próprio Ubuntu uma forma de se obter os tais codecs de forma automática (e outras "semi-automáticas").