I finally managed to track down and fix the bug that would sometimes cause Legionaries to no longer be able to be recruited, even if you had the required tech and buildings.
This bug was also responsible for Garrison Sizes sometimes becoming much smaller as a result of Legionaries and Vigiles no longer being included in the Garrison list.
This was a really tricky bug to hunt down because it would only show up after closing the game and then attempting to load a save that was made after researching the tech you needed to upgrade to Legionaries. A huge thank you to everyone who reported this bug, I almost gave up looking for it after trying to recreate it for the past week.
STIM 3.41 is a hotfix that everyone should download immediately to correct the bug, as it will effect the AI as well and therefore Rome's performance on the campaign map.
Unfortunately the hotfix will not correct the problem if you're attempting to load a save that has been made after the tech has already been researched, so you will need to either roll back to a save that was made before researching the tech, or start a new campaign.
Sincerest apologies!
-Silven
----EDIT----
Second hotfix posted, STIM 3.42. Read below.