Hi Oliver,
Your suggestion works fine, but obviously it's not going to do this for every connection which isn't ideal either. I've done some more investigation and I'm now not convinced that this is the correct solution, at least in this specific set of circumstances. The Solaris telnet client does not have this issue and running a packet trace I can see that when it connects it's negotiating quite a few telnet options with the remote server.
Net::Telnet::Options seems to allow this type of negotiation, although I've not had a chance test the theory yet. I'll be sure to post back if I managed to figure it out
Matt