Recentemente instalei o Listen no meu ArchLinux e não estava conseguindo escutar músicas no formato mp3 e ogg nele. Para resolver este problema bastou eu instalar os pacotes gstreamer0.10-mad e o gstreamer0.10-ogg. O primeiro é o responsável pelo suporte a mp3 e o segundo a ogg.

Para instalá-los, no ArchLinux, basta fazer:

# pacman -S gstreamer0.10-mad gstreamer0.10-ogg

NOTA: Se você não usa o ArchLinux, você pode instalar os pacotes acima usando o gerenciador de pacotes padrão da sua distribuição.

Obviamente, você só precisa instalar os dois pacotes caso tenha músicas tanto em mp3, quanto em ogg.