The message probably needs to be more explicit: "Voltairine de Cleyre isn't using the same safety numbers anymore. Probably this contact just has a new phone or reinstalled Signal, but you might want to confirm the new safety numbers with them.". And the accompanying icon should be an ! or ? or something.
I've been talking with people who haven't noticed when I change the disappearing messages on/off, which has the same appearance and displays in the same place as these advisory messages, so clearly some people are already ignoring them.
Threema does it with 3 dots red, orange ad green, but other versions of this might be experented with.
(Yes, it is open source, but most people don't have the knowledge or time to compile software themselves)
I still think Signal is one of the best secure messengers though.
Android: http://support.whispersystems.org/hc/en-us/articles/21463462...
iOS: http://support.whispersystems.org/hc/en-us/articles/21313245...
The cryptographers behind signal are very smart; they have thought about these things.
The signal model has the advantage of not having to trust a third party server. With iMessage, it's possible for the government to force Apple to add pubkeys to a user's identity (although the user will be notified).
When I updated my version it all worked out.
