Git Push ERROR: Repository not found

I am having a very strange problem with git and github. When I try and push, I am getting:

git push -u origin master
ERROR: Repository not found.
fatal: The remote end hung up unexpectedly

I added the remote:

git remote add origin git@github.com:account-name/repo-name.git

Any ideas?