Дело в том, что ZIP не предусматривает хранение в архиве информации о кодировке, в которой написаны названия файлов.
В убунте у вас utf8, а в винде соответственно cp1251. Отсюда и проблемы.
Можно конечно предварительно конвертить имена файлов в cp1251, тогда они будут на винде нормально прочитаны. Но например на какой-нибудь другой иностранной винде (с каким-нибудь другим cp1252 например), они опять-таки будут кракозябрами.
И универсального решения для ZIP нет и быть не может.
Пользуйтесь теми архивами, которые позволяют хранить информацию о кодировке файлов или для которых установлена кодировка, в которой должны быть имена файлов.
* Lion-Simba тыкает пальцем в сторону 7z.