So an update to this:
If I run the script manually using my own login it works. However if I try to sudo -su to the web server's username it never connects w/Net::OpenSSH. Which then leads to it failing the telnet part also.
I'm guessing its a permissions issue that the webserver is not able to do the SSH but I get no log entries indicating any problems.