Did you check the following keys in your web.config?
<add key="SMTPServer" value="localhost" />
<add key="SMTPRequiresAuthentication" value="false" />
<add key="SMTPPort" value="25" />
<add key="SMTPUser" value="UserName" />
<add key="SMTPPassword" value="UPassword" />
Also, take a look at your user.config file. If it has the above keys, those will take precedence over the web.config.
After verifying the keys, make sure you save the web.config (even if you didn't make any changes to it) so your web application will restart.
You also need to make sure the "Site Email From Address" is configured in Administration > Site Settings.