Finalmente trabalhei este aqui, esqueci completamente dos extras irrestritos.
sudo apt-get update
sudo apt-get install ubuntu-restricted-extras
Depois disso, reiniciei o Firefox e tudo estava bem.
Você pode verificar o status do seu codec de vídeo em:
Depois de instalar o pacote extras irrestrito, o H.264 e o MSE & H.264 deve ser azul com um cheque.