Наткнулся тут на утилиту написанную на питоне, которая перекодирует теги из cp1251 в UTF-8.
Работа с утилитой до безобразия проста. Утилита кладётся в директорию с музыкой и запускается.
python /home/username/music/tag2utf
И всё. Утилита рекурсивно проходит по всем директориям и спрашивает вас (по каждой директории) в какой кодировке там теги.
Так это выглядит: http://ipicture.ru/uploads/20101126/9E2RVS2T.png