Faced this problem when I created a remote repository with a README file to push an existing local repo. Should have just created without one as your git host suggests which went unnoticed. Created one without and problem solved.