Most host don't like giving access to SMTP, so that's my first guess.
Did you check the php.ini, specially:
sendmail_path <- did you move to a *nix platform?
sendmail_from
SMTP <- or still Windows based?
You running your own mail server? Many ISP filter out mail sent directly from a dynamic IP. AOL and MSN are know for doing this.
Those are a few thoughts, did they help?