Я не видел ваши кракозябры. Они разные бывают и один взгляд опытного человека может рассказать о проблеме.
Наиболее вероятная причина проблемы - в кодировке названий файлов. Большинство продуктов, рассчитанных на работу в русской M$ win, работают с кодировкой win-1251. Именно в этой кодировке хранятся названия файлов внутри архива. Увидеть, что это так, можно, открыв архив в шестнадцатеричном редакторе.
Я сталкивался с такой проблемой: создал архив в вин, пытался распаковать на раздел вин (нтфс). Хархивер вылетает, консольные архиваторы тоже не помощники. Архив благополучно распаковался на раздел линукса (ехт3), потому что он позволяет разный бред в названиях, в том числе : ? и даже перевод строки. Названия изменил руками.
Это только описание проблемы. Решение? Сам архиватор должен угадывать кодировку и приводить ее к ютф-8. Либо можно попробовать написать скрипт для пост-обработки названий. Можно написать еще свой распаковщик, сначала получить список файлов, потом извлекать их поштучно и с новыми именами. Или попробовать сделать конвертер для архивов с тем, чтобы новый архив открывался в любом архиваторе.