全く別の問題かもしれませんが、
私の環境ではAmarok2とExaileでファイル名に「#」の文字が入っているデータが再生できないトラブルがありました。
ファイル名から「#」を別の文字に換えたところ、問題なく再生できています。
また、この症状はmp3に限らず全てのデータで起こるようです。

なお8.10環境ではこの不具合は出ておらず、9.04固有の問題と思われます。