Heh, in my last South American native game I was wiped out by a joint venture of Spain and Portugal in 1482. That was cute.
In my last North American native game, Britain started colonizing the hell out of North America starting in 1524. They also decided to send 40k troops to establish "dialogue", which is a refreshing contrast to history.
In my last Siberian tribe game, I was under constant assault, sometimes by 7 nations at a time - many of them from (former) North American colonies of all places. Can someone explain why I, in Siberia, have to defend myself against the "United States of America", a 4 province colonial nation, in 1740? What exactly is the damn allure of Siberia, by the way? Had to abandon that game, not because I was losing territory, but because all of my provinces were under siege for nearly 50 years (at the cost of perhaps 10 million western lives through attrition due to massive fortifications and attrition stacking).
In most games I still see the Americas (North and South) almost completely colonized by the mid 1700s. Hell, by that time they're usually independent nations. The combination of both the colonial nation and the parent nation colonizing is enough to offset any new provinces.
If anything, Western colonialism starts way too early, is generally way too aggressive (except perhaps in the case of the Spanish), and is far more successful than it was historically.
Do you play on hard, with lucky nations, and AI bonuses by any chance? This is way different from anything I've experienced on normal without lucky nations/AI bonuses.