I'm a huge fan of GitHub but it is not with out it's problems. The following when anytime a push, pull, clone, etc fails it's usually because I'm logged in as the wrong user or GitHub is down. The following provide two quick tests to help figure out where the issue is.
Start by checking your ability to authenticate, if this fails ping the server.
ssh -T git@github.com
If authentication fails and the server returns a repsonse try checking your authentication again. If it still fails, you likely have an issue with your keys. For me I'm usally logged in as the wrong user or trying to sudo something.
ping github.com