Killer A's, after creating you have to load it from the MP screen FOR EACH PLAYER. After the first turn you can load normally.
You can not trust the level it says as this is often wrong, even when it says what you think it should.
The best way to check is to do a dry run with many human players and only 2 AI. Follow the method for the first turn, then just 'continue' through some more turns. By not settling cities only the 2 AI's cities will appear in F11. You can then tell the exact turns they found their second city.
On deity the second cities should be founded within a few turns as they get 2 settlers. On cheiftain they will take about 40 or 50 turns I think, as they have such huge growth and production penalties.