Не знаю, что это может быть. С локализацией у всех проблемы, всегда и во всем. Какие то "умные" люди придумали аж 5 русских кодировок, зачем?! Если бы все пришли к единой русской кодировке было бы проще, стран страдающих этим идиотизмом помоему не много, хотя я не проверял :). Так что привыкай писать транслитерацией везде и всегда :).Себе я поставил BMP(поддерживает скины xmms) и все в порядке, хотя... русскую музыку я не слушаю :), но в любом случае мне с ним проще просто по тому, что я сижу под Gnome.
Решения для тебя может быть два:
1. Найти другой плеер (их море и многие из них похожи на xmms). Если спросишь, "где искать?", попробуй в портах, это проще всего и работает наверняка.
2. Установить русский xmms из порта /usr/ports/russian/xmms, говорят, что в нем вопрос с русскими тегами решен, но я в этом не убедился (может, что не так сделал).
P.S. mp3blaster не пробовал? не плохая весчь. ;)