I suppose telnet session filed because on the system where script is running have version of OpenSSH 4.3, but Net::OpenSSH module need OpenSSH 5.4 and upwards for creating tunnels.
In case that i didn't have possibility to upgrade OpenSSH version is any alternatives way to create an ssh tunnel to gateway after that use tunnel to establish a telnet connection to remote host?
Comment on Re^3: Passing telnet commands through SSH
Is netcat or socat or any other similar utility available on the remote side? you can use then to forward stdio to some remote TCP server.
If Perl (or any other scripting language) is available on the remote side, you could also write your own netcat. See golf challenge: one-liner netcat clone