asmodeus: Connection established.
asmodeus: Sent key-exchange init (KEXINIT), wait response.
asmodeus: Algorithms, c->s: 3des-cbc hmac-sha1 none
asmodeus: Algorithms, s->c: 3des-cbc hmac-sha1 none
asmodeus: Entering Diffie-Hellman Group 1 key exchange.
asmodeus: Sent DH public key, waiting for reply.
asmodeus: Received host key, type 'ssh-dss'.
asmodeus: Host 'host2.mydomain.com' is known and matches the host key.
asmodeus: Computing shared secret key.
asmodeus: Verifying server signature.
asmodeus: Waiting for NEWKEYS message.
asmodeus: Enabling incoming encryption/MAC/compression.
asmodeus: Send NEWKEYS, enable outgoing encryption/MAC/compression.
asmodeus: Sending request for user-authentication service.
asmodeus: Service accepted: ssh-userauth.
asmodeus: Trying empty user-authentication request.
asmodeus: Authentication methods that can continue: publickey,keyboard
+-interactive.
asmodeus: Next method to try is publickey.
Permission denied at ./ssh_test.pl line 20 (#1)
    (F) The setuid emulator in suidperl decided you were up to no good
+.
    
Uncaught exception from user code:
        Permission denied at ./ssh_test.pl line 20
 at /usr/local/share/perl/5.8.8/Net/SSH/Perl.pm line 258
        Net::SSH::Perl::fatal_disconnect('Net::SSH::Perl::SSH2=HASH(0x
+888ac20)', 'Permission denied') called at /usr/local/share/perl/5.8.8
+/Net/SSH/Perl/SSH2.pm line 66
        Net::SSH::Perl::SSH2::login('Net::SSH::Perl::SSH2=HASH(0x888ac
+20)', 'user', 'password') called at ./ssh_test.pl line 20
Uncaught exception from user code:
        Permission denied at ./ssh_test.pl line 20
 at /usr/local/share/perl/5.8.8/Net/SSH/Perl.pm line 258
        Net::SSH::Perl::fatal_disconnect('Net::SSH::Perl::SSH2=HASH(0x
+888ac20)', 'Permission denied') called at /usr/local/share/perl/5.8.8
+/Net/SSH/Perl/SSH2.pm line 66
        Net::SSH::Perl::SSH2::login('Net::SSH::Perl::SSH2=HASH(0x888ac
+20)', 'user', 'password') called at ./ssh_test.pl line 20
[download]

The user/password it prints are the correct ones

It seems that your problem is suidperl. I don't have the experience to advise you on that one, but I believe that there are patches available to fix the problem. If you have root priviledges on the server that has suidperl, then try to disable suidperl. Good Luck!

Thank you for taking a look. I ran the find command from this page, and it didn't return anything on either local or remote server, so it does not look like suidperl is even installed.

OK, so I found that suidperl is installed on the remote server that the login failures are happening on. It is NOT on the local server, or the host1 which is working.

Because of the error that is given, and the difference of suidperl being installed, I am going to assume that's where my problem is at the moment. Unfortunately, I don't have enough access on the remote server to disable/un-install it.

From what I have read (admittedly a very fast read through), suidperl changes the user that the script runs as. I am confused as to whether it automatically runs it as root, or tries to make it run as the id that started the script on the local server. I suspect it tries as root because it doesn't even list user/pass pair in the auth methods it would attempt to try (root login disabled). Although, I did try and create a local id matching the login id of the remote server and running it that way, but still the same error.

I am confused as to why this would affect it before the login is complete though.

So, for the time being, I believe I am stuck. I'm off to learn more about suidperl and possibly Expect (and I've tried for two years to avoid Expect :-D ).

Thanks so much for the pointers, and if I come up with something new to try, I will post back and let everyone know how it worked out.