If it works on one system, but you get an error message on another, then it's probably a protocol problem. You might try using Authen::SASL. It's designed so that all protocols can share the connection.

Authen::SASL

For an interesting article on SMTP AUTH, see:

SMTP AUTH in sendmail 8.10-8.13