Another idea - @Kieran is working on a more generalised Invitation type of message (this is going to be used for social secret backups, and hopefully also for chessgames). What if naming and imaging was an invitation?

1. I send a private INVITION asking @Dan Hassan if he'd like to also be @Danny
2. If he consents, he publishes a public ACCEPT (which could also include the private key that would reveal the original invitation
3. Others seeing this could then be like "cool, we can call them Dan / Danny now".