Am I doing it wrong?

[Taedius]

You can only train your faction troops in your home provinces. Elsewhere, local troops are available.
The government types available also depend on your factions connection with the area.

Check out the FAQ.

[Zarax]

You need to demolish the roman government and build your own, remember that the farther from home you are the more you should rely on local levies (and higher government type).

[NIKOMAHOS]

Welcome to the fan or fun club JoeCool.

it would help you if you read the FAQ first.
You will learn for reqruitment, government systems, reforms, about different tempe complexes etc.

When you have installed EB you have also installed the EB recquitment viewer. If you open this file and spent a few minutes you will learn every reqruiment detail, in every provinse and for every faction.

Just in case you still have questions do not hesitate to ask. All member have the will to help new comers.

NIKOMAHOS

[Brave Brave Sir Robin]

Also notice the two different types of barracks. One for native troops, the other for foreign. In Carthage, the native barracks will provide you with all of your Punic/Libyan units while the foreign will give you access to Numidians and Maure. In Italy, you really won't get anything from native barracks but foreign ones will yield various Italian infantries, Greek units, and some Roman and Gallic units in the north. You will have to start relying on these more and more.

[Olaf The Great]

Also, some faction's troop recruiting areas are larger than others, Carthage's AoR is pretty small, reflecting their reliance on mercenaries, the Celtic roster spreads all over Europe. Rome, Hayasdan, and Parthia's AoR expands with reforms. It's been a while since I've played a nomadic faction, but I recall being able to recruit any unit anywhere on the map. Even with factions that have a massive AoR, you will still probably only be able to recruit the best units in your homelands, or in specfic zones(IE:Spartans in Sparta, British Swordsman in Camulosadae).