Three things I want to make the new world fun to play in, as a colonizer and as a native.
1) Dynamic colonial nations. We're getting that, with the Thirteen Colonies and all that. Time will tell if they half-ass it or not.
2) Horde-style colonization mechanic of native land. Edit: Plus the trade-post idea from Lolcats!
Good one <3
3) Have natives have a "population" number, separate from their provinces, to represent their nomadic nature (if they were nomadic) and the plagues from the old world that decimated natives. The plagues send the number down, events of colonists defecting to natives brings it up, and let natives move around their provinces like the migrate button, but for any size. You move out of one province, and into another, and the number of provinces you can control at any one time is controlled by your population number. You can double-up in one province or triple or more, so you can have 3 1-pop provinces or 1 3-pop province, or more.
Have a malus to economy from a newly migrated province (so it only provides a small amount until your population gets accustomed to the new province), local to that province. Like instead of giving 5 bucks per month, give 1-2, until a timer runs out. The more settled natives like the Inca and the Maya, and the Aztec, don't migrate, but they get a bonus to tech-rate or something to compensate. And give them the same population mechanic, because they were hit by plagues too, only instead of evacuating provinces, it lowers stability and economy unless they decide to consolidate into a smaller but more robust nation. (Instead of 5 1-pop provinces, have 1 5-pop province)
And a possible mechanic for reforming from a nomadic tribe to a settled tribe being need an admin tech of 3-4 (to represent the basic technology you would need to store food for a large population over winter) and a threshold of population in a single province (to make a city).
Hopefully all this can be modded with the addition of that migrate button, as long as it's not hard-coded to one-province-minors and you can add in some sort of seperate population counter/province-owner-ship.