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

Вариант 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/

URL: http://www.opennet.me/openforum/vsluhforumID1/55783.html#8
Обсуждается: http://www.opennet.me/tips/info/839.shtml

• Как переименовать имена файлов из одной кодировки в другую,baby11, 08:51 , 28-Апр-05
• Как переименовать имена файлов из одной кодировки в другую,Dmitry Pupkov, 14:32 , 03-Май-05
  • Как переименовать имена файлов из одной кодировки в другую,Peter, 14:53 , 16-Май-05
• Как переименовать имена файлов из одной кодировки в другую,sg, 17:09 , 13-Май-05
• Как переименовать имена файлов из одной кодировки в другую,igor chubin, 14:13 , 09-Июн-05
  • Как переименовать имена файлов из одной кодировки в другую,Саша, 01:44 , 27-Фев-08
• Как переименовать имена файлов из одной кодировки в другую,Виталий, 01:39 , 30-Июл-06
• Как переименовать имена файлов из одной кодировки в другую,Murz, 11:51 , 17-Янв-07
  • Как переименовать имена файлов из одной кодировки в другую,manson, 12:59 , 17-Янв-07
• Как переименовать имена файлов из одной кодировки в другую,Юзверь_Мастдайный, 12:37 , 26-Авг-10

Использовать утилиту convmv, делает все что нужно

А если нужно перекодировать rus -> translit?

>А если нужно перекодировать rus -> translit?
ну видимо надо пользоваться фичей кодировки КОИ: сначала в КОИ, а потом в latin1?

#!/bin/sh
#
# Script for file name charset conversion. It includes
# options for renaming, changing charset, recursive file
# name expansion.
#
# Syntax:
#
# chnamecoding [options] (file|dir)
#
# Brief help on parameters:
# -r | --recursive            - recursive
# -f | --charset-in            - charset of the input filename
# -o | --charset-out        - charset of output filename
#

# Script usage:
usage()
{
    echo "Usage:";
    echo "chnamecoding [-r | --recursive] [-f | --charset-in] [-o | --charset-out] (file|dir)";
    echo "-r | --recursive    -    recursive";
    echo "-f | --charset-in    -    charset of the input filename";
    echo "-o | --charset-out    -    charset of output filename";
}

# Exit if commandline is empty
if [ $# -eq 0 ]
then
    echo "Please specify argument list";
    usage;
    exit 1;
fi

# Init script startup variables
recursive=no;
charset_in="CP1251";                # default input charset
charset_out="KOI8-R";                # default output charset

# Analize input argument list
for i in $*
do
    case "$i" in
    --recursive | -r)
        recursive=yes;
        shift;
    ;;

    --charset-in=* )
        charset_in=`expr -- "$i" : '--charset-in=\(.*\)'`;
        shift;
    ;;

    -f=* )
        charset_in=`expr -- "$i" : '-f=\(.*\)'`;
        shift;
    ;;

    --charset-out=* )
        charset_out=`expr -- "$i" : '--charset-out=\(.*\)'`;
        shift;
    ;;

    -o=* )
        charset_out=`expr -- "$i" : '-o=\(.*\)'`;
        shift;
    ;;

    -*)
        echo "$i - Unknown option";
        usage;
        exit 1;
    ;;
    
    *)
        break;
    ;;
    esac
done

if [ $charset_in = $charset_out ]
then
    echo "Input and output charsets are the same";
    echo "===> Done.";
    exit 0;
fi

# Check for ICONV and input-output charsets
if [ ! -f /usr/local/bin/iconv ]
then
    echo "Can't find iconv executable";
    exit 1;
fi

# Check if input and output charsets are in iconv
# charset table
charset_avail=`/usr/local/bin/iconv -l`;

check_in=0;
check_out=0;

for i in $charset_avail
do
    if [ $i = `echo $charset_in | tr "[:lower:]" "[:upper:]"` ]
    then
        check_in=1;
    fi

    if [ $i = `echo $charset_out | tr "[:lower:]" "[:upper:]"` ]
    then
        check_out=1;
    fi
done

if [ $check_in -eq 0 -o $check_out -eq 0 ]
then
    echo "Invalid input or output charset found";
    exit 1;
fi

# File, and dir name processing
echo "===> Begin processing names..."

while [ $# -gt 0 ]
do
    dir=`dirname "$1"`;
    name=`basename "$1"`;

#
# Directory name conversion
#
    if [ -d "$1" ]
    then
        newname=`echo "$1" | iconv -c -f $charset_in -t $charset_out`;
        mv "$1" "$newname" 2>/dev/null;
        echo "==> Moving directory $1 to $newname";

#
# Recursive file name processing
#
        if [ $recursive = "yes" ]
        then
            find "$newname" -type d -execdir sh -c '\
            newname=`echo "$1" | iconv -c -f $2 -t $3`;\
            mv "$1" "$newname";\
            echo "==> Moving directory $1 to $newname";' {} {} $charset_in $charset_out \; 2>/dev/null
            find "$newname" -type f -execdir sh -c '\
            newname=`echo "$1" | iconv -c -f $2 -t $3`;\
            mv "$1" "$newname";\
            echo "==> Moving file $1 to $newname";' {} {} $charset_in $charset_out \; 2>/dev/null
        fi

#
# Single file name or mask name conversion
#
    elif [ -d "$dir" ]
    then
        find "$dir" -name "$name" -type f -execdir sh -c '\
        newname=`echo "$1" | iconv -c -f $2 -t $3`;\
        mv "$1" "$newname";\
        echo "==> Moving file $1 to $newname";' {} {} $charset_in $charset_out \; 2>/dev/null    
    else
        echo "=> File \"$1\" not found.";
    fi
    shift;
done

echo "===> Done.";

Вот так вот надо переименовывать:

find . -depth -exec sh -c 'a={}; mv {} ${a%/*}/`echo ${a##*/}|tr "[[:upper:]]" "[[:lower:]]"`' \;

Одной командой и сразу всё дерево.
Я здесь для примера написал как регистр менять.
Если кодировку, то просто ставите вместо tr, iconv
или recode, konwert

К вопросу о транслитерации.
Можете попробовать заменять так:

$ konwert UTF8-ascii/rosyjski
русский текст
russkij tiekst

Но результат получается с польским акцентом :-)

Пожалуйста, напишите по-подробнее про перекодировку всех папок в дереве..

Во втором скрипте надо писать:
find "$1" "*"

и далее по тексту

Что-то этот скрипт файло всё правильно переименовывает, а вот вложенные папки почему-то пропускает. А в остальном скрипт супер!

>Что-то этот скрипт файло всё правильно переименовывает, а вот вложенные папки почему-то
>пропускает. А в остальном скрипт супер!

Строчку
find "$newname" -type d -execdir sh -c '\
Заменить на
find "$newname" -depth -type d -execdir sh -c '\

А под виндовс никак низзя че-нить придумать?
получил тар архифф файлов с убунты - все файлы utf-8, вынь ессно utf-8 нихт ферштейн... :(