Como o iGama disse, não há um "codec pack", mas sim um conjunto de pacotes que podem ser instalados pelo synaptic ou pelo apt-get.
Não sei se o iGama citou todos os pacotes necessários, mas eu segui o tópico intitulado "Multimídia no Ubuntu 6.10 (Edgy Eft)!" do Galactus na parte "Dicas e Truques" aqui do fórum e rodo qualquer tipo de arquivo, inclusive H264. Alguns vídeos com o codec H264 podem ficar um pouco lentos se tiver cenas com muita variação - neve, chuva, etc, mas é pq o H264 é pesado mesmo. Algumas opções de otimização do mplayer conseguem compensar isso consideravelmente.