Heroku push rejected, Submodule install failed

The other answers are old.

As of 2019, you can now simply log in to Heroku and go here:

• https://dashboard.heroku.com/apps/<YOUR-WEBSITE-NAME>/deploy/github

And link your GitHub account or organization with Heroku. It'll then be able to clone private submodules your account has access to when selecting to deploy on a push to the master of your main GitHub repo.

I gave the answer as a comment to @jeffrey-k's answer, but now I'm even more sure of it, I'll write it here.

My repo suddenly stopped pushing, and these two things 'fixed' it:

1. Change all public submodule URLs (if any) from using the ssh transport URLs to readonly git transport URLs (i.e., from [email protected]:yaniv-aknin/public-project to git://github.com/yaniv-aknin/public-project). To do this, you will need to edit the file called .gitmodules in the root of your repo.
2. Remove all private submodules (if any) from my repo (remove them from .gitmodules and rm -fr their directories).
3. Commit the changes.

This handles these two changes in behaviour:

1. Heroku used to be able to clone submodules from github using the ssh transport (presumably they had some 'general heroku ssh key' and github account, but not sure).
2. Heroku used to ignore failed submodules and just continue the push.

I've opened a ticket asking if my analysis is correct and why did the change happen (with no warning I managed to hear of) - I'll update this answer if I learn something new.

UPDATE: Noah from Heroku's support replied to my ticket and largely acknowledged what I said above. Public repo URLs should be changed, private repos should either be removed or have credentials embedded in them as per this document; the latter solution has obvious security ramifications.