Git push failing after Heroku app name change

First Delete the Old remote

$ git remote rm heroku

Then Add the New One:

$ heroku git:remote -a newname

You need to change your git remote.

If you do git remote -v you should see heroku listed.

It will look something like:

heroku [email protected]:my-app-staging.git (fetch)
heroku [email protected]:my-app-staging.git (push)

Delete that remote...

git remote rm heroku

...and then add the new one

git remote add heroku [email protected]:my-app-staging-new.git