Sem mais idéias, infelizmente.
Talvez, como derradeiro recurso, fazer o upgrade para o Ubuntu 7.10, testado via Live CD antes (teste o som e o vídeo com os "exemplos" que vêm no próprio Ubuntu -- arquivos em formato ogg -- já que por padrão ele não toca mp3).
Também seria viável usar o novo LinuxMint Daryna, que toca mp3 por padrão e é baseado no Ubuntu 7.10. Com ele vc. poderia testar via Live CD as suas músicas em mp3.
O melhor seria uma instalação limpa, ou seja, apagando o Ubuntu 7.04 após feito o backup dos seus arquivos pessoais.
Boa sorte.