It's very likely that your new server does not allow mail to be sent from the web service. This could be because it blocks the SMTP port, or because it doesn't allow PHP to use mail(). You should be able to contact their tech support to ask. If not, you can try uploading your own PHP script that uses the mail() function and see what errors it gives you.
IMO, this is a good thing... web servers shouldn't be sending emails for a variety of reasons.
I would recommend using something like this: https://drupal.org/project/smtp
It will let you send email through a real email account, of course you'll have to make sure there's not a block on the port it uses.