Getting "The following submodule paths contain changes that can not be found on any remote" when they are in the remote

Hi, I'm getting very often, but not always, with many different projects using submodules, the message:

  The following submodule paths contain changes that can
  not be found on any remote:
    <module>

  Please try

  	git push --recurse-submodules=on-demand

  or cd to the path and use

  	git push

  to push them to a remote.

  fatal: Aborting.

This even happens after doing a:

git submodule deinit <module> rm -fr <module> rm -fr .git/modules/<module> git submodule update --init

So I am getting the reference from the remote, but when pushing a new change (that doesn't touch the submodules) I keep getting this error.

I tried to get more information about why this is happening but I couldn't. Googling didn't help either, so I'm resorting to ask here.

I would also like to report a tiny bug, when using push --quiet, I do get all the message above except for the <module> name, which is quite confusing.

$ git --version git version 2.9.3

(running under Ubuntu 14.04)

Please CC me, and thanks a lot in advance!