Solution :
I had faced the exact same problem in the recent past. The problem had occurred when I tried to clone using the HTTPS URL and after that I tried to push the changes using my Git Bash on the Windows using below command:
git clone https://github.com/{username}/{repo}.git
But, when I tried using the SSH URL as below to clone it, Above problem didn't occur:
git clone git@github.com:{username}/{repo}.git
OR
I had the same problem in the recent past, as I did not get any help at that time, so I have decided to post my solution that worked for me.
Few Points to remember :
1. The SSH key must be generated
2. The SSH key must be added to github.
3. After that I had created the new repository on GitHub for my project and followed the steps.
As the command line tool I used was the GitShell for Windows also I use Terminal.app on my Mac. The GitShell is the official GitHub tool and can be downloaded from the following link : https://windows.github.com/
Hope this solution helps someone who has the same problem.