Выходов их этой ситуации есть 2 выхода: научить плеер читать в cp1251 или перекодировать теги всей музыкальной коллекции в православную кодировку
я опишу первый способ, он быстрее и проще
cp1251 в rhythmbox для Debian Linux
1. Установим локаль ru_RU.CP1251
sudo dpkg-reconfigure locales
Здесь добавляем к выбранному ru_RU.CP1251
далее по умолчанию оставляем локаль ru_RU.UTF8
Теперь наша система знает вендовою кодировку
2. Теперь для запуска rhythmbox вводим в терминале
LC_ALL=ru_RU.CP1251 rhythmbox
Если не хотите все время вводить в терминале, то правим ярлык запуска на
/bin/bash -c "LC_ALL=ru_RU.CP1251 rhythmbox"
Теперь очищаем плейлист, загружаем в него заново все композиции и наслаждаемся русскими названиями песен