Если не переименовывать каталоги:

Вариант 1:
   find | sort -r | while read f; do
     fn=$(basename "$f"|iconv -f koi8-r -t windows-1251);
     [ "$fn" = "$(basename "$f")" ] || mv "$f" "$(dirname "$f")/$fn";
   done 

Вариант 2:

   #!/bin/sh
   # аргумент 1 - путь
   # аргумент 2 - из какой кодировки
   # аргумент 3 - в какую кодировку 
   find $1 -regex "$1/.*" | sort -r | while read f; do
      fb=$(basename "$f");
      fd=$(dirname "$f");
      nfb=$(echo "$fb"|iconv -f $2 -t $3);
      [ "$fb" = "$nfb" ] || (mv "$fd/$fb" "$fd/$nfb"; echo "$fd $fb -> $nfb";)
   done

Вариант 3:

   Использовать готовую программу для переименования с изменением кодировки http://j3e.de/linux/convmv/