Is it that hard for your users to click a simple link? I don't see how it can get any simpler than that.
As I said, the only time it will present a problem is if they no longer have a valid email address on file and if that's the case then sending the password reset email from the ACP to them will do no good anyway.
That's also why I recommended a notice to run for a short time.
All that link does is ask them for their email address that they registered with. I can see that it might be a problem if they can't remember their email that they registered with. In that case, they can do a "Contact Us" message and relay the info to you but then you can never be sure that the one requesting it is the user in question.
Odds are what has happened is they trusted their browser to remember it and the software change resulted in it not being input automatically. Not much you can do about that if they can't remember their email or their password AFAIK.