I was having similar problems with my upgrade from 4.0.2 -> 4.0.3, but i never spent much time troubleshooting- i just kept 4.0.2.
What i think the problem might be related to, is that when i installed zimbra i kept the primary domain as localhost.localdomain. Then via the web panel, i renamed that domain to myhost.mydomain.
if you have a similar situation, check this out:
http://wiki.zimbra.com/index.php?title=ZmSetServerName
ymmv!