I've just recently come across this problem with a CGI script. I am using PAR to load my libraries. The PAR file was created using the zip utility in Linux. I could unzip the file without a problem. I could run the zipcheck.pl script that is in the examples directory of the Archive::Zip package without a problem.
The very weird solution turned out to be renaming my cgi script to include a file extension (I was trying to use it without a file extension). It may be worth adding that the cgi script with no extension worked fine under Debian testing but was failing on my production server which is running Ubuntu Breezy.
William