I had the same problem. To find out if it was a php configuration problem I created a small testmail.php file (cut and pasted an example from someones site). That worked, proving that php mail() was working on my site. I wasn’t able to identify the problem but it must be somewhere in wp_mail.
A solution I found was to install Cimy Extra Fields and configured it for php mail (not smtp). It just worked. I didn’t spend time to figure out why.
