You know, this is the first time I've noticed that. I'll get in touch with CPAN about it tomorrow. For some reason, every time I run cpan interactively it gets the .tar.gz version. Perhaps you could blow away the .zip version and the cached cpan indices and try again. Or you could get the info-zip tools and re-configure CPAN.pm? I have no idea how to fix cpan's idea of where to get a module. I'd ask Andreas Koenig <andreas.koenig@anima.de> how that all works. Odd that it works for most everybody (I've never heard of this particular problem).

update: Or (which might be much easier), just grab the .tar.gz, unpack it somewhere, then go:

 perl Makefile.PL
 make
 make test
 make install # as root
[download]

update: After some thought, it looks like your CPAN.pm may be misconfigured. If you go o conf at the cpan interactive prompt, you can see its configuration. You should look at the settings for:

    build_dir          /usr/local/cpan/build
    cpan_home          /usr/local/cpan
    gzip               /bin/gzip
    keep_source_where  /usr/local/cpan/sources
    keep_sources_where /usr/local/cpan/sources
    tar                /bin/tar
    unzip              /usr/bin/unzip
[download]

and make sure that they're all correct. Especially make sure that unzip is set to something that can handle .zip files. It sounds like your unzip is set to point to gzip.