Thanks for all the feedback.
Looks like there was a little confusion.
We moved to a new server - NOT to a new domian.
so
www.ourdomain.com is still the same, we are just now on a new physical server.
the mail mail account hasn't changed and exists on the server.
I did see the note about the php.ini file but wasn't having much luck. I just thought I should check with the experts (you guys) first before I went to my server admins. Maybe it is something on their side.
We are having no other email issues (and have been on the new server for a week).
Thanks again for the thoughts/suggestions/help.