I experienced the same problem. I created a new repo and AFTER that added my SSH key. Push didn't work because of authentication failure. So I deleted the repo and recreated it again. Everything worked just fine :) Stange... So make sure you create your SSH key BEFORE creating a new repo.