What's the correct way to rename a heroku app?

Did you try heroku apps:rename NEWNAME?

Why use all caps?

heroku apps:rename my_new_app_name

Here is a great place to find out more:

How to rename your Heroku application

In case anyone is curious this method does not require any further configuration, your modifications should be immediate. At the time of this writing I was able to change the name of my app in seconds, and then do so again if I wished. Hope this helps.

heroku apps:rename new_name --app old-app-name

^ worked for me