well, generating a new password is a common method in retrieving lost password. since md5 is one way hash, in cannot be decrypted. consequently, a new password has to be generated when user loses his / her.
what to be considered deeply is to generate user friendly passwords. for example, mail.yahoo.com retrieving password by grabbing database which contains familiar words (with combination of special characters and alphanumerics) and pops a random password from the database. this is a better way instead of generating "meaningless" new passwords.
however, there is another way. that is to use two way hash. you can use, for example "base64_encode" and "base64_decode" combined with special function (to fuzzy up password cracker programs). with this method, user will never lose his / her password.
it depends on you to decide.