If you’re running Postfix, add this line to main.cf:

smtp_tls_security_level = may

Restart Postfix, and retry.

PS: You can set encrypt instead of may — but this can cause issues with Amavis and/or SpamAssassin.