Are there more than just one fingerprint for the affected server in known_hosts file?
When the host key algorithm is changed, a different fingerprint can result from this, existing fingerprints for that same server can cause issues, when only some are removed.