Looks like Google is now validating the TLS certificate received from the mailserver. So the hostname of the SMTP server provided in the GMail settings has to match the certificate provided by the server. I just updated the hostname in GMail and the problem is fixed now!
So for godaddy, where the securesever.net domain is on the tls certificate, how do i configure my outgoing which used to be mydomain.com but now fails?