One thing we've learned over the years is that security warnings should not be displayed to consumers under "normal" (eg. non-critical) circumstances, otherwise it creates a condition of "warning fatigue."
TLS certificate errors are not something that should happen under normal circumstances. When a TLS certificate fails to validate, something is really wrong. As we've gotten better about ensuring those conditions, browsers have made it harder and harder to get past the warnings, because they're not warnings anymore -- they're error conditions.
Key changes in a messenger are totally different. They happen under normal conditions, so putting them in people's faces by default has the potential to do more harm than good. If we can make them workable, systems like CONIKS or Key Transparency might be in our collective future, but if you don't like systems that are fundamentally "advisory" (don't tell you until after the fact), you're not going to like those new systems at all either.
For now, I think a fact of life is that most people will not verify keys whether the warnings are there or not, so I think what's most important is that the server can't tell who is and who isn't.
I'd love to hear other ideas about how to improve the UX of interactions like this, but I think they have to include a basis in the assumption that we can't fundamentally change human behavior and that we can't just teach everyone in the world to be like us.