I had the same problem , what I did was I first pushed it by force by using this
git push -f-force
I did this after I commited the files and was getting an error as you got.It did commit all the files and it pushed them. Then the next time I was pushing to the github .I did what it asked me to and it was alright then. Hope this works for you too :)