Running 4.08 beta, no other mods. I
think there may be some issues with the intersection between the new holding system, government type inheritance and the rules/AI behavior for upgrading from tribal.
This game started in 1000AD, with the pagan religions option, but no shattered realms. So Egypt is kemetic; the ERE is hellenic; western and central europe are reformed germanic (AI german empire reformed pretty early). None of them
started tribal. As far as I can tell, at some point a tribal vassal inherited the kingdom/empire/whatever, and the higher title became tribal and just stayed that way.
On a possibly-related note, it seems like the AI tends not to take the decision to upgrade villages when its available (at least within my empire - I haven't been watching holdings in the rest of the world that closely). Granted, I don't think I've ever let one sit for decades without upgrading it myself to see if the AI would get around to it, but there have definitely been some that have gone un-upgraded for at least a few months, if not a few years.
Also... either I don't understand what causes the first step of the city/castle building upgrade chain to appear in villages, or something about it is buggy, because a lot of village holdings in my realm (usually held by AI vassals) look like this:
I
think inheritance sometimes fixes this, and causes one or both of the upgrade chains to become available, but I'm not sure.