I mentioned earlier to check the configs "If Net::SSH::Perl is shelling out". I just looked at Net::SSH::Perl and it's a pure Perl implementation (i.e. not shelling out). That means you need to tell it what ciphers to use (i.e. it is not using ssh_config).

You might try running the server in debug mode (without forking) on a different port to get a better idea on what is going on. Seems like what your server is responding back with doesn't match the sshd_config file.