What about the MX record. You need to create one for the new domain at the public DNS. More details on getting the DNS setup right:
http://exchangeinbox.com/article.aspx?i=165
You may also want to test your DNS configuration with one of the many free DNS testing tools available online.
If you still have problems send an email from outside and post the NDR you get here.
Exchange Message Recalling Works! - http://www.windeveloper.com/recall/