I haven't dealt with that, yet, but since I store passwords the same way you do (encrypted in the database) my intention is to random generate a new password, change the stored password to the new encrypted one, then send them an email with the new random password along with a link to re-set the password to one of their own.
I am mainly responding to this thread so I will be sure to notice any replies that address issues I might not have thought of g