Brother peschkaj,
It may be worth your time to try CPANPLUS instead of CPAN.

Having rebuilt one of my Debian boxen recently, I found that CPANPLUS worked flawlessly for refitting the ~50 perl modules that I often employ, and that's from behind a Squid proxy.   I never had any luck getting the original CPAN module to work from behind a proxy.   8^(

There's even an introduction at "Perl Module administration with CPANPLUS" right here in the Monastry

I suspect that manually installing the following modules *before* CPANPLUS may have helped it go so smoothly for me.
Compress::Zlib
Archive::Tar
Archive::Zip
Test::Harness
Test::Simple
Storable
IPC::Run
MailTools
File::Temp
Term::Size

And like any good monk, you doubtless already know that ritual:
Fetch and extract the module tarball
perl Makedfile.PL
make
make test
make install
    cheers,
    Don
    striving toward Perl Adept
    (it's pronounced "why-bick")