Make sure you set and use the proper email routines. I had the same problem, and I only use joomla locally, but, it fixed when I used the SMTP and filled in the correct host user and password info. The only other problem I had to resolve, because this is used primarily as an intranet, was allowing Joomla through my firewall.
Found here: http://forum.joomla.org/index.php/topic,109745.0.html
Do searches on Joomla.org’s Forum and you can find answers to just about anything.
FYI: You can swith it so that there is no need to send the email for registration in the Global Config, but it isn’t advisable. 😮