maybe I can offer you some assistance. This may be a restriction by the hosting provider. Are you using hostgator by chance? Many are turning off the ability of php to send emails with the builtin command. Damn spammers making it harder for us!
Anyhow, if you are, look for the plugin called Cimy Swift SMTP. Here’s a link for you: http://wordpress.org/extend/plugins/cimy-swift-smtp/ . When I was with hostgator I had to run this plugin to get wordpress to send any emails.
Hope this helps mate. I know how frustrating getting something working can be.