Amigos.
Depois de instalado os codec eu reiniciei sim.
O link que eu postei ja faz isso tudo de forma automática, se clicarem no link e descer um pouco a barra de rolagem vão ver uma frase "Se você usa a versão 32bits do Ubuntu, clique aqui" clicando onde é indicado as instalações são feitas uma a uma. Por isso acredito que ja estou com todos os codecs instalados, só não entendo o pq dos vídeos não reproduzirem corretamente.
Obrigado pela atenção.