I went into the descr_strat.txt and moved everything from the "unlockable" section into the "playable" section. By default, there's only 5 factions you can play in your first game, but I was starting with Byzantium, dammit!