Are you a steppe faction? I think they can only get to city level on the step but to large city if you have a 'settled city'. If this is the case (or you are using the CityMod) then the message will appear if your faction can upgrade to the next level at all, even if their is a restriction in your area, hardcoding.