Public bug report changed: https://launchpad.net/malone/bugs/27086 Comment: I have solved this problem myself. The issue was that Evolution was not sending an FQDN as the argument to the HELO directive during the SMTP conversation. When I edited /etc/hostname and /etc/hosts then I was able to send email just fine.