Yes, SMTP code 535 is authentication.
Perhaps you can try selecting "Authentication" on the outgoing server as "SASL PLAIN" or "SASL LOGIN".
Oh, and it always helps to post server settings (server name / port / encryption, not the login or password obviously) with issues like that.