It sounds like your permissions aren't configured correctly on your new webhost for starters; a look at your Master Settings -> Primary -> Basic Tab -> Advanced Mail Configuration may be useful, a standard setting of "mail" would use the configured PHP email handler which would just send mails off to sendmail.
