Another route is to go back and just grab state from actual history. Science fiction writers do this all the time. You can come up with some pretty interesting ideas/nations/NPR's that way.
An African power based on any of the successful sub-Saharan African states would be a good place to build an African TN state. Mali, Songhai, the original Zimbabwe, the Zulu, Kush or Nubia would all be pretty good starting points.
Ancient China is both pretty fascinating from a historical perspective, and gives you some great Asian empires to base a TN state off of. They might even break the "China will have bad things happen in Aurora" curse. The Zhou, Qin, and Han periods are great places to start to build off of. Or you could pit break away modern factions in China against each other, there are a lot of ethnic and cultural/language groups in China.
Central Asia had some pretty fascinating historically significant empires that still have some cultural resonance today. There are some pretty cool to read histories on some of the more "colorful" states that emerged there. The Huns, The Avar, Pechenegs, Bulgaria, Cumania, Ghaznavid.
If you want something that fits with the current themes available, you had central asian empires like Baktria that had a majority Persian/Turkic population with some Greeks thrown in, and they used Greek military ranks and titles. Or Pontus, which was an Anatolian Persian (Persian commander names) state that adopted Hellenic culture (Greek Ship theme/ranks).
You could also postulate something like a collapse Mexico leading to an anti-western "revival" of Aztec culture. Or a similar one for the Maya, which could pick up southern Mexico and the rest of Central America. With a bit of optimistic extrapolation and/or conquest, you could get them to a decent enough population base.
