Update / Solution:
I found the solution.
The issue was that the leaderboard cannot be submitted on its own, even though it seems possible from the UI and documentation.
What worked for me:
Create a new app version
Add a Game Center-enabled build
Add the leaderboard to the same submission
Submit both together for review
After doing this, the leaderboard was accepted and works in production.
So the key point is:
The build and the leaderboard must be submitted together in the same review.
Hope this helps others!
Topic:
Graphics & Games
SubTopic:
GameKit