You've just described a "man in the middle" attack. It is endemic to any public key cryptosystem, including Signal and PGP, not just WhatsApp. The notification that you see in WhatsApp, Signal, SSH, PGP, or whatever is the defense.
> PS: I just check on my phone if those notifications were turned on. There were not. And I'd never turn those off myself, which leads me to conclude that the rekeying notifications are off by default (in their android app)
Key change notifications are off by default in WhatsApp. That's probably going to be a fundamental limit of any application that serves billions of people from many different demographics all over the world.
Even if they were on by default, a fact of life is that the majority of users will probably not verify keys. That is our reality. Given that reality, the most important thing is to design your product so that the server has no knowledge of who has verified keys or who has enabled a setting to see key change notifications. That way the server has no knowledge of who it can MITM without getting caught. I've been impressed with the level of care that WhatsApp has given to that requirement.
I think we should all remain open to ideas about how we can improve this UX within the limits a mass market product has to operate within, but that's very different from labeling this a "backdoor."