Just one complaint. I believe you said that these would not be separate nations? Many players here want to be able to play as a colony, including me (I love the colonial game), and this would be perfect for representing it.
Of course, tags would be a problem. I'm thinking names should be dynamic (players can choose colony and revolutionary names, but AI will use from a list of reasonable ones), but there could be a large number of generic tags that they are assigned from. To give an example, I go straight for the Caribbean, and then later roll over the Aztecs. I set up two colonial charters, naming them Columbia and Cortez. When my competitor (say it's France for this scenario) shows up in the Caribbean, they set up New France. All three of these nations would be tied to a random tag, Tag1, Tag2, and Tag3. If it's necessary to manage AI and prevent using up all of these free tags, there could be a distance limit on planting down these centers (so that I can't place one in Manhattan and one in Connecticut, for example).
But there are also other factors. That would represent the colony itself excellently.
CLAIMING LAND
To claim land you simply march your conquistador through it, but there would be distance limits (it would have to be so close to a dependent colony, and could be a further distance from a self-sufficient colony). So when my first batch of colonists arrive at New Orleans I can stake out part of Louisiana, when I get a self-sufficient colony it would expand more, and once the colonial charter is established it would extend to cover a country-sized area or more. The main purpose of this is conflict. The first nation to lay down claims (represented by a lighter shade of your national colors) would have the right to evict competitor colonies, and any secondary nations (lines) can do so but with penalties. As England I can't just sail down to Brazil and plant my flag, but I can plant it all over the Ohio Valley, since it's nearby.
NATIVES
North Americans would benefit from (some) Horde mechanics. When I move into Iroquois and Cherokee land, I shouldn't automatically colonize that land, it should revert to "the wild". South Americans and Mesoamericans are probably fine as they are, though, as I understand the Spanish basically just took over administration from the previous establishment.
"Wild" natives would be better if we had some diplomatic tools. I'd recommend having them produce some amount of goods (things like Furs and foodstuffs) and also consume some (the white man's goods). We should be able to do things like arm the natives of a province against encroachment, ally with our own through trade, and play them against each other to lower the population. First contact (conquistadors landing) should cause a ripple effect of Smallpox utterly destroying their numbers. There was a civilization along the Mississippi River valley that was just as magnificent as the Aztecs or Maya, but it died out from the disease before explorers arrived to write of it. In fact, it would be great to have several more native empires, and have special event chains dealing with the collapse of their civilizations (first your manpower and tax drops to nothing, then you take huge Stability hits, and finally places start reverting to wild).
Also, natives ought to be allowed to colonize similar land (I have the same opinion of African natives). I don't know what kind of special mechanics would exist, but I imagine it would be done through both war and settlement. It should be expensive but entirely possible.
CLASSES
Forgot to mention. While everything else should be moddable, I doubt this one would. There ought to be something like four different classes, basically whites, natives, and blacks (with blacks being purchased on the markets or produced from provinces). There could be boni to having different kinds. If revolt risk, culture, and all that was divided between the three classes, we could have things like a slave rebellion and the option to exploit resources more efficiently. Resource-wise, different terrains and colony types would require different types of population.
Let me use the big three colonial powers as an example. New England is specialized for production and a balanced economy, which benefits mot from whites. Thus, the reasonable policy for the motherland would be getting settler numbers up as much as possible (Natives and Blacks can't work in factories or the like, and are rebellious, so you have every interest in running them off). Dixie and the Caribbean, though, are tropical/subtropical cash crop zones. Whites drop like flies, and Natives aren't that good either, so you want to import large numbers of Blacks. When you get into Mexico or the Andes, though, you want to mine all the minerals you can, so it's good to work your Natives to death to extract as much as possible.
