Had the same issue as AdamBoyle, some domains would work some wouldn't, turned out that the domain that wouldn't was named as mydesination setup back on page 2 of the tutorial:
postconf -e 'myhostname = server1.example.com'
postconf -e 'mydestination = server1.example.com, localhost, localhost.localdomain'
Just put a www. in front of the domain, don't know if that's a good thing to do or not but it worked.