Must agree on national spells not castable by national mages.
To Sombre:
Mictlan - and what on Crocodile warriors?

Tien Chi - I see they are a great nation as they are, but you asked about all nations!

And fighting monks would be too similar to Warriors of 5 Elements, so I mentioned them only as an example... Of course, they would work, but won't add much..
Machaka - well, Zulusi actually DID use two-headed spears!

And African "throwing irons" are certainly weird enough, but I don't know what their stats should be, especially as chakram got so sucky ones. They also used many versions of swords, but these should all probably be equivalent to broadsword/falchion. Also they sometimes used a parrying club in left hand, but this probably wouldn't work... Another idea could be a unit with Seasonla power.. And what did you mean about Hyena? (there is also a possibility to rise up something from African Tertian fauna - as Nature summon or Death Enchantment...)
Bandar Log - they already have quite a few kinds of Bandar infantry. Elite Bandar should either get something special, or they won't be taken by anyone as normal Bandar are already stronger than normal human infantry, but even elite ones won't be on par with Vans or Abyssians...
Pythium - unfortunately, it uses Republican Rome as basis for its troops, not Byzantium. I would be glad to make it more Byzantian, but think it goes beyond the scope of this mod. And Vans, even infantry, I think would be almost the same degree of 'too much' as communion troops. Also, Pythium already has solid infantry. Maybe adding 'gladiatorial animals' other than Hydras would be better idea?
To All on Man:
Having no MP experience with it, I still tend to think of it as a solid nation. Also, I think that they were given weaker infantry specifically to compensate for greatness of Longbowmen. However, 'Witch' for me associates with dark (read: Death/Blood) magic. Maybe they should get some?