I recently setup a second GitHub account for some personal unrelated use. I wanted a new project to use that account instead of my default one. I added the origin as normal and tried to push:

$ git remote add origin git@github.com:my-new-account/project.git
$ git push -u origin master

ERROR: Permission to my-new-account/project.git denied to ethanmick.
fatal: Could not read from remote repository.

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

Whoops! Okay, wait, yeah. This makes sense. I hadn't setup any SSH authentication for my new account yet, and didn't want to use HTTPS. I'll just create a new SSH key and add it to my new account. Following GitHub's docs I quickly create a new key and add it to my account. Cool, show time.

$ git push -u origin master

ERROR: Permission to my-new-account/project.git denied to ethanmick.
fatal: Could not read from remote repository.

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

Wait a moment, this is how it should work! What gives? Okay, so instead of sending the correct SSH key on the request, it's still sending the key associated with my main account. I need to fix the request to send the right key.

Some searching around gets me there. I can edit my ~/.ssh/config file to send the correct SSH key in the request to the host I want, in this case, GitHub.com.

# Main Account
Host ethanmick
User git
HostName github.com
PreferredAuthentications publickey
IdentityFile ~/.ssh/id_rsa

# New Project
Host my-new-account
User git 
HostName github.com
PreferredAuthentications publickey
IdentitiesOnly yes
IdentityFile ~/.ssh/id_rsa_new_account

Next, I need to edit the origin URL to tell it to use this new configuration:

$ git remote set-url origin git@my-new-account:my-new-account/project.git

Instead of using github.com as the host, set it to the value of the Host field in the SSH config. This tells the request to use the values in that SSH configuration, correctly pointing to the new SSH key. It will now push!

However, there was one more gotcha. When I pushed to the new repo, with the new SSH Key, Git still used my globally configured username and email! This meant GitHub thought the commits were coming from my old account! Time to set that to the values on GitHub:

git config --local user.name "New Account"
git config --local user.email "email@example.com"

And then everything worked perfectly.