I found a number of similar issues reported but they were all closed without, in my opinion, meaningful resolution.
fatal: Could not read from remote repository.
Please make sure you have the correct access rights
and the repository exists.
fatal: clone of 'git@github.com:my-org/my-repo' into submodule path '/home/circleci/project/my-repo' failed
Failed to clone 'my-repo' a second time, aborting
It turns out, that it was logging in via a Deploy Key, but that key naturally cannot access other private repos. I also added an Additional SSH Key for github.com but it isn’t used because the deploy key matches first.
My solution was to run ssh-add -d in order to remove the deploy.
Hope this helps someone else - i wasted a few hours on it…