@Buster: You have to move a general into the new cities for one or two turns at least, which counts more or less as pacification of a region. Then you get the option to build Monarchy, Oligarchy or Democracy government buildings, which in turn enable the Barracks to be built.
@Gen.jamesWolfe: I don't really understand - did you conquer those parts of Syria and India and in turn Lydia conquered you? Or is it a bug and it happened automatically?
@decimator22: I will write a temporary workaround for this bug. Once it's there I'll send you a PM