Request password gives page not found

Request new password feature sends an email with a one-time login, but the URL in the email gives "Page Not Found" error. I have found similar reference on this topic here http://drupal.org/node/31153, but this was Drupal 4.* and I am using Drupal 6.15, (and I don't have mass_url module installed).

The email contains a link (format seems to be ok):
http://example.com/user/reset/4/1267425150/c85e803301d2e6bffa6d39d647f1d550
but it generates "Page Not Found" error.