Caro inor..
Estava com o mesmo problema. Eu usava o Ubuntu na versão 9.4, tentei muitas coisas tbm, até q um dia consegui instalar os codecs, porém ficava travando os videos, a solução eu encontrei quando fiz a atualização do Ubuntu para a versão 9.10. Após instalar a nova versão, a primeira coisa que fiz foi tentar asssistir os filmes, quando abriu o Reprodutor de video do ubuntu, o próprio reprodutor informou que precisava de codecs, pesquisou e pedio que eu fizesse o upgrade, resumindo instalei os codecs que o reprodutor informou. E agora funciona tudo.
Atualize seu OS.
Atualização via Rede para Ubuntu Desktops (Recomendado) -- Usando a internet
Você pode facilmente atualizar através da rede seguindo os passos abaixo.
1. Iniciar Sistema/Administração/Gerenciador de Atualizações
2. Clique no botão Verificar para verificar novas atualizações.
3. Se houver quais atualizações para instalar, use o botão Instalar Atualizações para instalá-las e pressione Verificar após terminar.
4. Um mensagem aparecerá informando você da disponibilidade de uma nova versão
5. Clique Atualizar.
6. Siga as instruçẽos na tela.