I can login.  But if users forget their password they can't retrieve it.

Yes, it successfully sends the test email and sends email on other things (notification of new user sign outs, notification of user lockouts, etc.).  It just appears to be the "Forgot Password" function that doesn't send an email.

Now, the functionality appears to work partly.  If I type in a non-existant username it says the username doesn't exist.  However if I type in an existant username, it comes back with the message saying the password reminder can't be sent now.

Yes, 100% sure that the account is not locked. 

The error I get is different than the one in the link.

I get an error saying:

Password could not be sent at this moment. Please try again later or contact the site administrator.