Do you have the GNU gzip utility ? (try running gzip from a shell prompt)
If it is not installed on your system you can grab a copy here and install it (and take the .Z package):
- http://hpux.cict.fr/hppd/hpux/Gnu/gzip-1.3.3/

Then launch perl -MCPAN -e shell and type o conf init to reconfigure CPAN and take care when it ask you for the "gzip" program path ...