Программа zip не очень правильно работает с национальными символами в именах файлов. Чтобы потом распаковать архив, созданный, например, под Windows, нужно сделать следующее:
unzip <archive>
convmv -f iso8859-1 -t cp850 -r --notest --nosmart <arch_dir>
convmv -f cp866 -t utf8 -r --notest --nosmart <arch_dir>
Это при условии, что локаль utf8. Если koi8-r, то в последней команде это нужно отразить.
Собственно основную работу выполняет утилитка convmv, предназначенная для преобразования кодировок в именах файлов. Находится она в одноименном пакете.