Password is not available for custom AMI

Hello

We had an instance with the pem file lost. Now I've generated a custom AMI from it following the guide.
I've created a new instance i-0ab5bce81b25cc541 from the AMI with all configs preserved as the original instance.
Now trying to connect to the new instance it says "Please wait at least 4 minutes after launching an instance before trying to retrieve the auto-generated password.".
After reading many docs and answers, it seems that the solution is to login with the original password, but as I said the pem file was lost.
Basically I get a logical conflict situation - the guide says to generate a new instance with new pem file, but use the old password for login.

Thanks