Are you using a network install of WordPress?
Are you using a SSL certificate?
Are you using any plugins that might override the default WordPress actions for resetting a password? (you can test this by disabling all of your plugins and testing to see if the problem still exists, if it goes away, then one of your plugins is causing the issue)
I’m not using network install, and I don’t think I have a SSL certificate. I’m using Theme My login if that helps.
If you disable Theme My Login, does the issue still occur?
Yeah, I disabled all my login boxes and it continues.
Does it have to do with the default template?
I would not know. You should probably try the plugin support page, since it’s a plugin specific issue: http://wordpress.org/support/plugin/theme-my-login
I’m not sure I understand your question.
I used to have difficulties with notification e-mails, and those problems got resolved after my host told me what to enter at Dashboard > Settings > Post via e-mail and I had installed, activated and configured “WP Mail From II” (plugin):
http://wordpress.org/plugins/search.php?q=WP+Mail+From+II
Maybe that will help.