Кратко: 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

Перезагрузим плейлист.

Врубаем музон, радуемся, пьём коньяк.