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.