A primeira coisa que um novo usuário tem que fazer assim que instala o Ubuntu é instalar o pacote Ubuntu-restricted-extras e pronto. Não precisa de mais nada.
O Ubuntu não é como o Windows, onde você baixa um programa e ele já vem com os codecs prontinhos. É mais fácil. Ele já tem os programas, mas por uma questão legal os codecs mp3 e outros não vem juntos. Mas isso até a última versão, 10.04. Pois na futura 10.10 já é possível instalá-los ao instalar o sistema pela primeira vez, basta ter conexão com a internet ok, claro.
Digo e repito. Não precisa de Medibuntu, nem de colocar para tocar e só depois ir baixando a medida que os novos formatos (.mp3, .avi, .rmvb) vão aparecendo. O Ubuntu mudou, vamos acompanhar essa mudança. Está mais fácil. Baixa o ubuntu-restricted-extras e pronto. Até o acesso ao Banco do Brasil, tão sofrido, vai junto nessa.
=]