All right, I was wrong.
It was possibility #2 (see above).
I was using Java SDK 1.4.2
The project that I was trying to implement on my machine has yet to be tested with Java 1.5.
However, I updated to v1.5 and the java.util.zip worked perfectly.
My guess is that java sdk 1.4 does not support all of the latest zip encryptions.