Some Time there is a shallow update not allowed issue in your cloned GIT repo.
This means that you have to unshallow your repository. To do so you will need to add your old remote again.
git remote add origin <path-to-old-remote>
After that we use git fetch to fetch the remaining history from the old remote (as suggested in this answer).
git fetch --unshallow origin
And now you should be able to push into your new remote repository.
If you see
fatal: couldn't find remote ref refs/head/master
, you must rungit push origin HEAD:master
first.