Desde 11,10 não vi necessidade de ter medibuntu, pois basicamente todos os formatos estão no pacote "Ubuntu Restricted Extras". Pelo menos nos vídeos e formatos de música comuns. No seu caso, o formato mp3.
O que eu faria é remover o medibuntu ppa. Em seguida, acesse o Centro de Software e procure restricted
Você deverá ver um pacote chamado "Ubuntu Restricted Extras". Instalar este pacote (ou reinstalá-lo se você já fez) e depois de instalado você deve ter suporte para arquivos mp3. Você será capaz de ouvi-los.
Para mim, está trabalhando aqui e em outros 3 PCs.
A única coisa necessária é o pacote Restricted Extras.
Eu também gostaria de salientar, apenas no caso de alguém perguntar por que remover o medibuntu ppa. Eu tive um problema semelhante ao MP3 mencionado aqui. O problema foi uma certa confusão entre os pacotes Restricted Extras e Medibuntu. De alguma forma, houve uma guerra de formatos entre eles. Foi resolvido removendo o medibuntu e usando apenas o que o Ubuntu tem. Neste caso o restrito.