I just started getting this message yesterday on a server that has been running fine for years, to my knowledge nothing has changed on the Ubuntu server recently and the Zimbra version has been stable also for a while (8.0.2 network). Only thing possible is some network provider changes (ATT). All of my users are seeing this when they try to send an email:

This is the mail system at host mail.cbrworld.com.

I'm sorry to have to inform you that your message could not
be delivered to one or more recipients. It's attached below.

For further assistance, please send mail to postmaster.

If you do so, please include this problem report. You can
delete your own text from the attached returned message.

The mail system

<xxxxxxx@mac.com>: host 127.0.0.1[127.0.0.1] said: 504 5.5.2 id=03268-01 -
Rejected by next-hop MTA on relaying, from MTA(smtp:[127.0.0.1]:10029): 504
5.5.2 <localhost>: Helo command rejected: need fully-qualified hostname (in
reply to end of DATA command)
"Hostname -f" shows the correct name (mail.cbrworld.com) and "postconf | grep myhostname" returns same. Any help in where I should start looking would be appreciated.