1650:
Vikings: Quebec, Newfoundland, Nova Scotia, the Hudson Bay, East coast down to about Delaware. Has opportunity to expand into Canada and the Great Plains.
Rome: East coast from Virginia down to Florida, Along the coast of Lousiana, Texas, and Mexico, the Caribbean, Mesoamerica, Colombia, maybe Venezuela. Has opportunity to expand into the Rockies and Great Plains or conquer Incas. Or they could be in the middle of conquering the Aztecs and Incas.
Byzantium: East coast of S. America from Guyana to about Uruguay. Has opportunity to expand into Central Brazil.
China: West coast of N. America from about British Columbia to Northern California, Hawaii, maybe Alaska. Has opportunity to expand into Canada and the Rockies.
Japan: Southern California to tip of Baja Peninsula, West coast of S. America from below the Incas to Tierra del Fuego. Has opportunity to conquer Incas or expand into Central Brazil.
Should the rest of the world have anything? And what's going on in the Old World?
I really don't know much about what the AI does when settling. The only game I've really gotten far with is Song China. It's 1589, and no one else has settled the Americas mainly because the Vikings keep losing cities to revolutions, Rome and Byzantium are conquering the germanic tribes, and Jpan hasn't even discovered astronomy. (They were nice enough to steal all the goody huts, though.) I've settled from Vancouver to Sacramento, and the east coast of Australia. By the way, I like the Impis you put in Australia and New Zealand to represent the Aborigines and the Maori.