Quanta memória RAM você tem? Eu sempre tive a melhor sorte com o VLC no Ubuntu. Você ainda precisará certificar-se de ter os extras restritos instalados. O Ubuntu não vem com os codecs de mídia para reproduzir muitas coisas, a menos que você marque a caixa.
Você pode descrever o que torna o mp3 não -listável? Você também pode fornecer algumas capturas de tela do monitor do sistema durante a reprodução? Esses podem ser seus drivers de áudio, mas quero ter certeza de que seu processador não está sendo atingido pela decodificação primeiro.