You are correct in saying that Aboriginals and many other so-called "primative" Natives were not nearly as primitive as many seem to think-(edit incorrect grammar)Then we could get around to discussions of Maori tribes and Australians, because both of them make way more sense once Natives actually work in the region.
However, while the Aboriginals did have all these things, I am yet to hear a compelling argument for adding a nation tag. Nation tags should require a centralised governmental organisation of some kind, which I am yet to hear an archeologist tell me. Many North American Tribes, like the Iroquois did have some kind of government, in their case having a council and organising border tribes to have armies. I'm not saying the Aboriginals didn't have a form of government, merely that I am yet to see one as organised say, as the Iroquois.
As for New Zealand, Maori have only lived there for about 200 years at game start, and definately do not deserve a tag then. By the time they get to a point where they might deserve one, they are fighting the Musket wars while European colonisation blooms around them. If it was decided that these brief Maori empires to become tags they would be very short lived, And would only have existed for 30 years, Starting at the very earliest in 1807(1820 would be a better date) and through to the 1840s, and personally, I wouldn't give a tag to them then anyway, because these 'empires' collapsed on the death of their conquerors.