git push heroku master error: Repository not found

Inside your project folder go into .git/config and look at what (if anything) is defined under the heroku remote.

For example, one of my apps has:

[remote "origin"]
  url = [email protected]:jefflunt/cortex.git
  fetch = +refs/heads/*:refs/remotes/origin/*
[branch "master"]
  remote = origin
  merge = refs/heads/master
[remote "heroku"]
  url = [email protected]:cortex-cedar.git
  fetch = +refs/heads/*:refs/remotes/heroku-cedar/*

...where origin is the github repo, master is the master branch on github, and heroku is the name and path to the repository on heroku.

It's important that (a) you have an entry for heroku because that's what makes your push work, and (b) that it's pointed at the correct path/repo.

To get the path/repo for your project go into you application settings on heroku and it should be listed.

On a side note, these lists of remotes in your .git/config file are what make the aliases that you use on the command line work at all, and the names they are given are simply found in the config file.