I was getting very much the same error only with a twist:
I'm setting my zimbra server up in an existing environment that already has DNS, MX records, etc, all set up. It looked like the install script was seeing the hostname of my zimbra server as the domainname - the error looked like this (I've changed the details, but everything was correctly-formatted FQDN info):
DNS ERROR resolving MX for zimbra.foo.example
It is suggested that the domain name have an MX record configured in DNS
Change domain name? [Yes]
Create Domain: [zimbra.foo.example] foo.example
Prior to that, I tried entering rubbish as the domainname, and it correctly let me know that it couldn't find an MX entry for 'sdklfjslfj.sd0vnwe0hf' or whatever I typed. Giving the correct domain name caused the error to go away, but the support person I spoke with on the phone suggested that this is a bad idea for some reason.
OK, what gives? I'm guessing that somewhere in my config (I'm a debian and suse guy - redhat is my least-favorite distro, and therefore I know little about it's internals), I've got an error, but where?
/etc/hosts has a localhost entry and a proper FQDN entry for the zimbra server
/etc/sysconfig/network has a correct HOSTNAME entry
the "domainname" command returns correct info.
Also, it's worth noting that the MX entry for this domain is not and will not be the IP address of the zimbra server - we use a hosted barracuda service for spam and virus hosting, and even when I drop that (ugh, can't happen too soon, believe me), the zimbra server will have an internal IP address and only get inbound traffic through forwarded ports from the firewall.