OK, let's start with this:
let's see how you get on with that setting. If that doesn't help then increase it by ten per-cent until you get to 80% - don't go any higher.
zmlocalconfig -e tomcat_java_heap_memory_percent="50"
Let's also check your basic DNS settings while we're at it, do the following on the zimbra server:
and post the details.
host `hostname` <-- type as-is with backticks not single quotes
dig yourdomain.com mx
dig yourdomain.com any
You realise that FC4 won't be supported in the upcoming Zimbra release 5, don't you? I assume you'll also be wanting to upgrade Zimbra before that?