Sempre usei o Amarok e ouço normamente minhas músicas mp3, alias só tenho mp3 no micro.
Bom, quando instalei usei o Amarok que estava nos repositórios. Instalei todos os codecs da dica que lhe passei.
Você instalou pelo synapitc? instalou todos os codecs?
Usa outros player (Xmms, Banshee, Audacious Songbird e outros)? Se usa, toca mp3?