gmail-unencrypted-tls

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

smtp_tls_security_level = may

Restart Postfix, and retry.

gmail-encrypted-tls

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