Had the same problem, but fixed it for my system. Basically it was my mail tansport system (MTA) that was misconfigured.
My system is debian linux, using exim4 as the mail transport agent. Looking at the logfile /var/log/exim4/mainlog showed that i had a bad smarthost. Once I reconfigured it with 'dpkg-reconfigure exim4-config' it all worked fine. For those with similar setups, here are the steps with my answers.
1) at a terminal: dpkg-reconfigure exim4-config
2) Split configuration into small files? no
3) General type of mail configuration: mail sent by smarthost; received via SMTP or fetchmail
4) System mail name: blue.gruz.net (gruz.net is my machine domain name, doesnt really matter what you put there)
5) IP-addresses to listen on for incoming SMTP connections: 127.0.0.1
6) Other destinations for which mail is accepted: blue.gruz.net (again, doesnt really matter)
7) Machines to relay mail for: (blank response, leave it blank unless you really know what you are doing)
8) IP address or host name of the outgoing smarthost: mail.internode.on.net (my ISP mail server, use your own)
the rest of the questions are irrelevant to this issue.
3) and 8) seem to be the important questions.
This was my second go at WordPress, this problem being the showstopper before. I think the one thing that dragged me back was being able to see pictures of new themes at work, phpbb2 wouldnt do that, so i came back and gave it a second try.
Now, I can go back & delete all those junk users i created while trying to get it to work! Hurrah!