I'm a bad person for not using debug...thanks lamp.

The debug pointed something out, that was later clarified by this thread -> http://www.cpanforum.com/threads/851.
It appears that Cisco have some buggy implementation of SSH2 that would not allow multiple channels, so Net::SSH::Perl fails at opening a second dummy channel.After making some changes in SSH2.pm (explained in the thread above) to cope with Cisco, it connects just fine.

Thanks again!