Для этих целей существует отличная программа convmv.
Ставится она из репозитория довольно просто:
sudo apt-get install convmv
После чего вам просто необходимо указать папку, в которой необходимо совершить переименование файлов из одной кодировке в другую.
Например, мне нужно переименовать файлы из KOI8-R в UTF-8 рекурсивно вниз.
Делается это так:
convmv -r --notest -f koi8-r -t utf-8 Folder/
Опция --notest отвечает за переименование.
Т.е. без этой опции вы просто сделаете тест и посмотрите как файлы будут «выглядеть» в нужной кодировке.