You can have an Proconsul's/Imperial Palace and without an Army Barracks to train Praetorian Cohort. Of course, if those towns are at that level, then they would almost certainly have an Army Barracks. Of course if you just had Marius...I guess your recourse is to just train Praetorian Cohort as your garrison Nobody is taking that town. I rarely use gladiators or Arcani, are your gladiators not retraining either?