Can you try using another email address .. like a yahoo or gmail one as maybe it's your ISP or shared host which has an issue with mails from our server.
Also, please see possible configuration issues under "general and order processing issues" section in the troubleshooting page.
