TLS just enables encryption on the smtp session and doesn't directly affect whether or not Postfix will be allowed to relay a message.
The relaying denied message occurs because the smtpd_recipient_restrictions rules was not matched. One of those conditions must be fulfilled to allow the message to go through:
smtpd_recipient_restrictions =
permit_sasl_authenticated
check_recipient_access hash:/etc/postfix/filtered_domains
permit_mynetworks
reject_unauth_destination
To explain those rules:
permit_sasl_authenticated
permits authenticated senders through SASL. This will be necessary to authenticate users outside of your network which are normally blocked.
check_recipient_access
This will cause postfix to look in /etc/postfix/filtered_domains for rules based on the recipient address. (Judging by the file name on the file name, it is probably just blocking specific domains... Check to see if gmail.com is listed in there?)
permit_mynetworks
This will permit hosts by IP address that match IP ranges specified in $mynetworks. In the main.cf you posted, $mynetworks was set to 127.0.0.1, so it will only relay emails generated by the server itself.
Based on that configuration, your mail client will need to use SMTP Authentication before being allowed to relay messages. I'm not sure what database SASL is using. That is specified in /usr/lib/sasl2/smtpd.conf Presumably it also uses the same database as your virtual mailboxes, so you should be able enable SMTP authentication in your mail client and be all set.
Best Answer
The other server, is it one of yours or does it belong to some other domain?
I usually like to use online tools like this link MXToolbox to verify my own mailserver. Make sure everything is kosher and not on any black list. Then you will need to look at the reject mail server. I don't rememeber if it was this error, but I've had to send emails to various domains such as AOL etc to have them whitelist my mail server.
You might want to do a google search for: 554 5.7.1 Postfix
And although you may believe that nothing changed on your end, you may want to double check you config files. Have a look at a few of these links for ideas and hints... How to correct Postfix' 'Relay Access Denied'? http://ubuntuforums.org/archive/index.php/t-502884.html http://support.microsoft.com/kb/895853/en-us