I'm not sure how your IP addresses and DNS are setup on this virtualized server, but I had some similar issues getting zimbra installed on a RHEL 4 inside of vmware. Turned out I had two issues relating to DNS. I had a real IP address pointing to the server, but it came in through NAT on the host.
1) I needed to make sure that /etc/hosts properly listed localhost for 127.0.0.1 and the name of my server mapped to its internal IP address. This is described in the zimbra install docs.
2) I needed to get BIND running as described here
http://wiki.zimbra.com/index.php?title=Split_DNS
After that I needed to use the zimbra admin console to flush all of the messages once. Then it worked like a charm.