A client was recently having this error in the “Mail App” on their android phone after setting up with our email.  I knew it wasn’t an issue with our server, but the timing was uncanny.  This error prevented any outgoing mail, but only to certain domains, one of which was Gmail.  Eventually, I found that it goes back to an option to “encrypt all outgoing emails.”  To disable this option, and stop receiving the error  go to (in the Mail App):

settings->account settings->the account you’re having trouble with->more settings->security options

Simply uncheck “Encrypt all,” and everything should be peachy.

I suspect that setting up an email account using SSL or TLS may automatically turn this option on on some phones, though I’m not sure.