Well, about Palmyra, I wrote something about Palmyra, so I can say that I know the thing quite well, and therefore I like it, although it's not too correct in the screenshot, for gameplay issues, that's ok

. My Idea with the trade still stands, you haven't have commented on it. ..
About the Nabateans:
A quick google gave this pic. (btw. You have to insert two words, only petra will you give just pics of women .... )
Petra
I can't tell you much more but what I know from my head. This is cause I don't have books ready to cite...
But around that time (Scenario) the nabateans were the merchants of the world. They controlled the trade route from the meditterannean to South Arabia (and from there to India). They were competing with the Ptolemeans above that monopol (the way through Mesopotamia wasn't the best choice at that time). The Ptolemeans tried to conquer them a few times, as well as they are thought to establish trade ports at the red sea and more south. But the Nabateans had to fight the Ptolemeans hard because the trade was their base of life. They lived in your map in the southeast corner. At the eastern shore of the red sea and in the deserts around that region. They actually were a desert people. (the picture above shows their capital Petra).
I hope I've helped a bit...
mfG mitsho
EDIT: didn't see your question: Egypt was Ptolemean. --> a Monarchy with some aristocracial inputs.

Carthage, I THINK, was under a senate. Meaning they had a sort of republic of the aristocats. I have to look at the first page to be able to tell you exactly what governments (because I don't know which exist in this mod...)