Как ты формируешь строку байтов для записи в ZipOutputStream?
Распечатай эту строку побайтово, посмотри, как в ней представлены русские буквы. Может быть, они портятся ещё до сжатия.
Вот код архивации:
    String s = "1.htm";
      FileOutputStream f =
        new FileOutputStream("test.zip");
      CheckedOutputStream csum =
        new CheckedOutputStream(
          f, new CRC32());
      ZipOutputStream out =
        new ZipOutputStream(
          new BufferedOutputStream(csum));
      out.setComment("A test of Java Zipping");
      // Хотя нет соответствующего getComment().
      for(int j = 0; i < 1; i++) {
        System.out.println(
          "Writing file " + s);
        BufferedReader in =
          new BufferedReader(
            new FileReader(s));
        out.putNextEntry(new ZipEntry(s));
        while((c = in.read()) != -1)
          out.write(c);
        in.close();
      }
      out.close();