Just as an idea... since we're operating on the assumption that European history has gone vastly differently than it historically did...
Why not put in Vinland as a viable state in the Newfoundland/Labrador/Isle Royale region? We could still keep most of North America open to colonization by withhoulding any chance of explorers or conquistadors until the Europeans have a chance to get there, and limiting their map knowledge to those limited areas and Greenland and Europe....
Another oddball one - once we get to the rest of the world - what of the possibility of the Chinese having sailed north or east instead of south? (Discovering Siberia or Hawaii, perhaps? Or even the Aleutians?) Might be too disruptive to let them access the American mainland, though....
P.S. I'm currently playing my second Aberration game, this time as Granada; having taken and converted up to Gascogne and Rousillon by 1600 (and Corsica; I lost Tangiers to Genoa early and when I took it back, I really pounded them and they offered Tangiers and Corsica, so I took it), I'm now faced with a 3-province Bourbonnais, a huge Burgundy (which controls, among other things, about 50% of Gaul), a 7-priovince Savoy (having taken Provence, Lyonnais, Dauphine and Helvetia) and a vassal Morocco as my only borders. And I've just seized five new Christian provinces to convert - Poitou, Languedoc, Guyenne, Auvergne and Cevennes. My only comment so far - seeing that the Granada events are still being worked on - is that a lot of the new "fantasy" revolters - and indeed some of the older ones too - have very early shutoff dates, so the number of vassals I *could* release is now very limited. And I was so looking forward to releasing and restarting as a Muslim state in southwestern Gaul...
In fact, I'm half tempted to ask for a tag for a Muslim emirate of Gaul (or something along those lines) - except for the fact that I don't see a way to force the game to permit it to exist only if the provinces it revolts in are already Muslim.