I updated my PS from 1.6.1.18 to 1.7.5.0 using an update module from addons. And realised that I couldn't login using my customer account. And of course, I had the same error when resetting the password, the password reset link was expiring instantly.
I don't know if other cases are the same, but I manually copied the ps_customer database from PS1.6 to PS1.7 because I didn't want to lose some tables.
In PS1.7 I see 2 new tables in ps_customer (reset_password_token and reset_password_validity). I'm guessing that's why the link expires so soon because without this tables it can't set a value. So I manually added these 2 tables from phpmyadmin (structure->Add 1 column(s) after date_upd) with the values:
reset_password_token -> type varchar -> length 40 -> default NULL -> collation utf8_general_ci
reset_password_token -> type datetime -> default NULL
Tried the reset link, works like a charm!
Also, if a customer cannot login after the update to PS17, the solution is to copy from PS 1.6 settings.inc.php the values from 'cookie_key' and 'cookie_iv' and putting them in the new and improved app/config/parameters.php file.
And for the database, update passwd from the old length 32 to the new length 255:
update passwd -> type varchar -> length 255
And when I try to login again to my customer account it worked with the old password, I didn't need to reset the password anymore.
Hope it helps.