перекодировка mp3-тэгов из win-1251 в koi8-r

Есть GTK прога easytag, она поможет

Можно еще с помощью скрипта copytag (он и рекурсию поддерживает)

ИМХО если уж перекодировать, то перекодировать в стандартную кодировку для соотвествующей версии тагов. А там ни cp1251 ни koi8 не было и никогда не будет. Если лениво, то можно посмотреть на rusxmms.sf.net, там есть патчи для нескольких популярных библиотек, чтобы кодировка определялась на лету и теги выводились в нужной.