As mentioned later in this thread, the problem in the routers is opening a second channel.

I had the same problem with ssh'ing to PIXes, and to get them working, I made the following changes to Net::SSH::Perl::SSH2:

sub login -> removed the code to open a "dummy channel"

sub client_loop -> change the check "last unless $oc > 1;" to "last unless $oc > 0;"

After making these changes, I am now able to open a Net::SSH::Perl connection to a PIX configured to only support ssh2. I'm not quite sure why the dummy channel is needed, perhaps servers disconnect once the channel count goes to 0.