So why did this happen?
Changing the app name also changed the Git URL. Particularly the remote. What was first:
Particularly painful when you have outstanding changes pending a commit.
Understood, how do I sort this?
Luckily that's the easy part - as soon as you know how ;-) Execute the following two commands:
$git remote rm heroku
$heroku git:remote -a my-new-name
And now try your Git commit - Phew!
Stick to either command-line or GUI - especially when you are new to things. Saves a lot of time :)
And for completeness, here's how you rename your heroku app from the command line.
Have fun playing with Heroku!