How to inform plugin users that a plugin has changed name?

From what I can tell, it’s impossible to change the name of a plugin once it has been uploaded to the repository. I have a plugin called simple-nav-archives, and I’m expanding it to be able to list archives in places other than the navigation, so obviously, it needs a new name.

However, there are currently thousands of people (if the download count means anything) who use my plugin, and I want them to switch to my new one, but I’m not sure the easiest way to facilitate this transition.

Here is what I’m considering:

Current Strategy: Upload the new version of my plugin with the new name to the repository. Then, create a new version of the existing plugin that displays some sort of semi-annoying message on the plugins page informing the user that simple-nav-archives is no longer being supported and there is a new version with a new name by the same developer.

Is this the best option? It seems like there must, or at least should, be a better way.