The first steps to debugging this are to run the following (on the zimbra server):
Code:
host `hostname` <-- backticks not single quotes
dig yourdomain.com mx
dig yourdomain.com any
and post the output.
If this is a DNS problem then you should look in the logs (including the initial install logs) to see what errors you've got.