Our e-mails to a Zimbra client keep getting rejected. below is the log from Zimbra. We checked and all our settings seem to be correct, and our e-mails get delivered fine to most e-mail servers. Any ideas?

Oct 22 13:05:23 zimbra postfix/smtpd[19586]: connect from mail.zanadia.com[]
Oct 22 13:05:24 zimbra postfix/smtpd[19586]: NOQUEUE: reject: RCPT from mail.zanadia.com[]: 504 5.5.2 <ds5029>: Helo command rejected: need fully-qualified hostname; from=<abcd@zanadia.com> to=<arne@abcdefghi.com> proto=ESMTP helo=<ds5029>