Afinal o problema com a reprodução de mp3 no Fedora Core 4 não tinha nada de novidade. Facilmente encontrei na Internet a descrição e respectiva resolução deste problema. Estranho foi o facto de apenas ontem essa reprodução ter sido desactivada depois de algumas semanas a usar Linux e o xmms. Talvez tenha sido algum período de trial, o que, sendo um caso de licenças e patentes, também não acho muito normal.
A resolução foi bastante simples, bastou instalar o rpm xmms-mp3 (que se encontra facilmente com o google) para tudo voltar à normalidade. Ainda bem, porque estar a converter toda a minha colecção de mp3 para ogg vorbis ainda era coisa para demorar algum tempo.