Github Authentication Failed - ... GitHub does not provide shell access

$ git remote add origin [email protected]:lut/EvolutionApp.git
fatal: remote origin already exists.

$ git push -u origin master
fatal: 'EvolutionApp' does not appear to be a git repository
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

My keys were added succesfully

 $ ssh -T [email protected]
 Hi lut! You've successfully authenticated, but GitHub does not provide shell access.

The Github article https://help.github.com/articles/generating-ssh-keys/ says that "Shell access" should not be an issue? What could the problem be?

Try and redefine the ssh url for remote origin:

git remote set-url origin [email protected]:lut/EvolutionApp.git

And try again.

Only git remote set-url can change an existing remote URL (as opposed to git remote add, to add a new remote name and URL)
Here, is issue was the URL of the existing origin: EvolutionApp: it needed to be replaced by a valid one.
Using git config url."ssh://[email protected]/".insteadOf https://github.com/ would not have helper, considering there was no HTTPS URL in the first place.

You can add this in the ~/.gitconfig file.

[url "ssh://[email protected]/"]
        insteadOf = https://github.com/

Now ssh will be used instead of https.

You might have to add the remote again. That error message happens when Git doesn't know where to push to.

Use git remote -v check if the remote exists, if not, add it.

Even then if it doesn't work try removing the GIT_SSH environment variable, this maybe causing the problem.