First step would be to switch to the default Magento template, then see if the password reset emails are working. If they do, then it's most likely an issue specific to your template.
If it still doesn't work, it could be an issue with the local email server settings itself.
For emailing issues, I would recommend installing SMTP Pro by ASchroder.
https://github.com/aschroder/Magento-SMTP-Pro-Email-Extension
After installing:
go to System > Configuration > System (under Advanced)
Open SMTP Pro Email General Settings
For Choose extension option
select SMTP
Set Log all messages
to Yes
Expand the SMTP Pro Email SMTP Settings
section
Set Authentication to None
and leave Username
and Password
blank (this is assuming the apache user your Magento is running on is allowed to send emails through SMTP. If not, you should enter in the correct SMTP login settings for this area.
Set Host
to localhost
and Port
to 25
Save your configuration, and then click Run Self Test
under the SMTP Pro Email General Settings
section.
If the test was successful, password reset emails should now be working. If the user did not receive the email, it may of either been blocked by their incoming mail server, or filtered into their spam folder. If you have access to your server's mail logs, you can see if the emails being sent from Magento are being accepted by the mail servers they are being sent to.
You can view a log of emails being sent from Magento under System > Tools > Email Log
after this extension is enabled and Log All Messages
is set to yes in the configuration.