> when the user gets the message from their SSH software that says "Warning! This SSH fingerprint has changed" ... that would happen whether it is by password or by key.

You have already sent the password to the mitm already.