Have you tried using the network utility app yet? Use the lookup tab and check to make sure your domain name matches your ip address and see if you can look up your mx record. So what I usually do is
1. Check server.mydomain.com - see if it is linking to your ip
2. check ip and see if you get the reverse look up
3. check your mail server (mine is mail.mydomain.com) it should link back to your fully qualified domain name.
I just did a fresh reboot and I was having the same issue. So in the server admin (download from apple - http://support.apple.com/kb/DL1419) under:
DNS -> Zones create a CName (alias) under your fully qualified name for your mail server (MX record).
After that my email was working fine.
Hope this helps