Não sei qual é o player de vídeo que você está usando, mas recomendo usar o VLC, pois ele inclui seus próprios codecs e, portanto, lida com praticamente qualquer formato de vídeo.
Você pode instalar o VLC entrando no Ubuntu Software Center, procurando por VLC e, em seguida, clique em Instalar.
Como alternativa, você pode ter certeza de que instalou todos os codecs corretos entrando em uma janela de terminal e digitando:
sudo apt-get install gstreamer0.10-plugins-ugly gstreamer0.10-plugins-ffmpeg