In the case like me that you aquired a repo and are now switching the remote origin to a different repo, a new empty one...
So you have your repo and all the branches inside, but you still need to checkout those branches for the git push --all
command to actually push those too.
You should do this before you push:
for remote in `git branch -r | grep -v master `; do git checkout --track $remote ; done
Followed by
git push --all