Updating just in case somebody else runs into this issue in the future.
Our island had no promotion for about 10 days. Then the bug that prevented us from publishing a new version was fixed, and after we uploaded a new version our game started being promoted by the discover system normally again. So it was indeed a bug, but uploading a new version seems to be the fix.