Easytag, если нет противопоказаний. Заодно причесать не только кодировку, но и содержимое тегов.
RusXMMS в противном случае: /etc/apt/sources.list: deb http://rusxmms.sourceforge.net/ubuntu/rusxmms dapper main apt-get update apt-get install librcd librcc audacious, ctrl+P (диалог настроек), "список воспроизведения", "Автоматическое определение кодировки для": Russian -- ubuntu-ru mailing list ubuntu-ru@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-ru
