Нам потребуется программа python-mutagen, для её установки в консоли набираем:

sudo apt-get install python-mutagen (можно установить и из Synaptic)

Переходим в папку с подопытными файлами:

cd <путь к папке, в которой находятся файлы, подготовленные для перекодирования тэгов>

И запускаем перекодировщика:

find . -name "*.mp3" -print0 | xargs -0 mid3iconv -e CP1251 -d