Кратко: PPA для самой свежей версии Audacious
sudo add-apt-repository ppa:nilarimogard/webupd8
потом, разумеется
sudo apt-get update
sudo apt-get install audacious audacious-plugins
Audacious может некорректно обрабатывать кириллические теги.
Запускаем его, идём по пути файл/настройки/список воспроизведения,
"автоматически определять кодировку для языка" ставим "русский",
а в поле "если не удалось определить использовать кодировку" вводим
utf-8, oem866, windows-1251, cp1251, koi8-r
Перезагрузим плейлист.
Врубаем музон, радуемся, пьём коньяк.