I'm trying out the "Mammoth Lords"--although honestly, that's unlikely to be the title I settle on.
Anyway, a few details of what the setting's like:
1) Start by taking a "calque" of North America in roughly 975 A.D. or so, during the highpoint of the so-called Viking Age of Europe. In this setting, travel across the Atlantic will probably be constrained by a brief period (a few years) of exceptionally (and possibly supernaturally formed) cycles of winter storms and other bad weather, effectively isolating North America from Europe for at least a few years. As in other calques, such as Robert E. Howard's own Hyborian age, the Warhammer world, or Paizo's Golarion, I'm not using literal historical groups of people or countries; when I say, for example, Viking, it's understood that I'm using my fantasy version of Vikings, not actual ones.
2) First major difference from real history that I'm imitating; the Viking age here is considerably more "Golden" than it really was; there were more vikings, going to more places and just generally "doing more" than they really did. They've discovered North America and settled it successfully almost immediately, building a number of colonies on the East Coast of Canada the the Northern Seaboard that are still thriving. This doesn't mean that they are all united into a single kingdom; I can see analogs of Knud's North Sea Empire, an eastward looking Kingdom of Sweden and allied Rus states even further east from there as all part of my "Viking Golden Age." Well; fantasy equivalents, rather, of course.
3) The second change major change is that the Vikings, being more successful and widespread than in real life, may have migrated, or caused to migrate, other European populations or refugees. Therefore, there are also population pockets in the New World of Slavs, Saxons, Scots and Irish. Given the heavy Viking settlements and integration in England, Scotland and Ireland anyway, this isn't too much of a stretch--think of the Northern Sea Empire of Knud the Great as a sustainable one and you're mostly there. Keep in mind that by the end of his life, almost all of Knud's closest inner circle were Englishmen and not Scandinavians, too. Anglo-Vikings, Anglo-Norse and Gall Ghaedil and other hybrid Scandinavian peoples, as well as flat-out Englishmen, Scotsmen and Irish who were allied with the Vikings (and Wends too--Knud's grandfather was Mieszko I of Poland, after all) have moved all across the globe, and in most instances still cling to their local culture as they've done so. This way I don't have to get fatigued by too many Old Norse names all the time.
4) Because this is the Bølling-Allerød interstadial, the animal life of Europe and North America is quite a bit different than what we have today. The Great Plains of North America are much like the savanas of Africa; native North American lions, sabertooths, scimitar-tooths, short-faced bears, wolves, coyotes, pumas, "cheetahs" and dire wolves all hunt several species of native horse, ass, "zebra," pronghorn, bison, giant peccaries, giant camels, long-legged llamas, giant sloths and even two species of mammoth (up north the Wooly mammoth, and down south the Columbian mammoth, which is, essentially, just an elephant. Mammoths and living Asian elephants are more closely related to each other than either are to the African elephant) and mastodons. A handful of other fictional critters such as predatory diurnal hunting bats and whatnot, complete the scene.
5) I'm going to assume that the historical populations from the 1600 and 1700s just get pushed backwards in time and get used anyway. Those are the only real Indian populations that we know enough about to calque anyway. Therefore, the Vikings, Saxons and whatnot can interact with the Five Nations of the Iroquois, the Algonquins, and the classic, well-known tribes of Plains Indians, such as Apaches, Comanches, Sioux, etc. With different names, of course.
6) There are hints that the Chinese may have also "discovered" America. In this setting, they have, and also have colonies on the West coast.
7) The Moundbuilders are a nation, or group of nations, still extant in the east central part of the continent. Although some nations, such as the Cherokee and other Iroquois speaking nations, may have some link with them, they purposefully keep seperate; the mound builders are feared and shunned as dark shamans and sorcerers of ill-repute. They appear to be a hybrid culture of native american and stragglers from Atlantis.
8) As the last entry hints at; I'm not at all opposed to throwing in plenty of overtly fantastical elements into the stories. Dark wizards or shaman, ghosts, demons, malevolent spirits; all of these will feature prominently in any stories set in this setting.
Another bit of info, adopted from my very bare wiki:
Northern Europe (although probably not Scandinavia) would be ice free, and calqued cultures similar to the Vikings and others would be present and accounted for. Taking another page from Howard, I'm not using "real" nations, cultures and peoples, but transparent "calques" of them.
Africa would also be considerably different, as the Bølling-Allerød coincided with one of the "Green Sahara" phases. Lake Chad would have swollen to be larger than the present day Caspian Sea, and the Sahara would be largely grassland with antelope, elephants, giraffes, and riparian life and civilization that included crocodiles, hippos, and villages of people who lived primarily by eating fish. If you take the water erosion theory of the Sphinx seriously, then some kind of proto or pre-Egyptian civilization lived on the Nile. If you remember Howard, you'd expect something like Stygia anyway--his "fantasy" Egypt.
In North America, the Berengia corridor would be open. Although sea levels were higher during the Bølling-Allerød than they were during either the Older or Younger Dryas periods, they still were not as high as today. All of the "lower 48" would be ice free, as would much of southern Canada, and a corridor of land east of Canada's Coast Mountains. Much of the Great Basin and American southwest deserts were not as dry during the the late Pleistocene as they are today, so places like Monument Valley, for instance, would be largely wooded, not unlike the Kaibab National Forest today, instead of the much dryer scrub desert that prevails over the canyonlands region today. Huge pluvial lakes, like Bonneville, Lahontan, and the Manly lake system (that, among other things, completely flooded the Death Valley region) as well as numerous relatively smaller but still quite large lakes would have dotted what are today desert regions of the American west. Florida, the Yúcutan and the isthmus of Panama would both be quite a bit wider than they are today. Massive Lake Agassiz, holding more water than all the freshwater lakes in the entire world today, sits in south-central Canada as a freshwater cool inland sea formed by meltwater from the retreating Laurentide ice sheet. Although no one in the setting itself would know this, Lake Agassiz is a bit of a time-bomb waiting to happen; when the ice-wall that separates its waters from the Hudson Bay finally breaks, the catastrophic flooding and draining of Lake Agassiz, over the course of just a few months, the massive influx of water into the Arctic Ocean led to rapid climate change and the Younger Dryas cooling and glacial advance.
The Sunda shelf would be much less submerged than it is today, so much of what is today the East Indies would actually belong to a much greater Malaysian peninsula, up to the Wallace line, at least. New Guinea, Tasmania and Australia would all be connected as the continent of Sahel, which has its own unique megafauna, including giant komodo dragons (Megalania), thylacines, thylacoleos, giant wombats, giant-short faced kangaroos, and other unusual life forms.
The Spartel Bank, off the coast of the Gulf of Cadíz, has only recently been submerged by rising sea-water at the end of the Older Dryas, creating a diaspora of its advanced inhabitants known as Atlanteans. Although this would be entirely whimsical, and nobody believes that these sunken continents have seen the light of day in over 20 million years, lowered sea-levels during the Ice Ages or not, I think it would be fun to have the sunken continents of Zealandia and Kerguelen breach sea level too; they can be the "lost continents" of Mu and Lemuria, doomed to sink again as sea levels rise following the Ice Age--they are in fact undergoing quite the crisis currently, since the Bølling-Allerød is quite a bit warmer and has quite higher sea levels than during either the Older or the Younger Dryas periods that bookend it. When Lake Agassiz floods the Arctic Ocean, these two continents will go completely underwater, and while sea levels will drop again during the Younger Dryas, these will not re-appear; the Muans and Lemurians are undergoing the early stages of their own diaspora, following in the wake of the Atlanteans (who occupied a much smaller landmass anyway) who went through it more recently.
How much of this geography would be known and relevant to any characters in this time frame? I'm not sure exactly how cosmopolitan I intend to make it, but since a false "Golden Age" of the Vikings is another influence, certainly I think it's possible that characters may have been in eastern Europe, the Eastern seaboard of North America, into the interior of North America (where I really plan on having the action center), and possibly north Africa. Any "Chinese" inhabitants on the farther side could have been as far south as the Wallace Line without raising eyebrows, and of course, the American Indians themselves are fairly recently spread from Berengia too, in this scenario. In fact, they are newcomers relative to some of the older peoples living in North America; the peoples affiliated with the Spirit Cave mummy or Kennewick Man, for instance, who have been described as showing physiolocial similarities to the Ainu or far-flung Austronesians. This makes them colonists from Mu; in my setting, much of the people who later emerge as Austronesians are descendents of Muans genetically, if not linguistically, and the stone heads on Easter Island are the last remaining artifacts of their existance from a far flung colony (Zealandia does not extend nearly as far as Easter Island). It's entirely possible that plate tectonics doesn't actually work at all in this fantasy version of Pleistocene earth, which frees me up to do all kinds of geographic catastrophism theories if I want to. Because, let's face it--they're dramatic.
Like Howard's Hyborian Age, I want fantasy cultures, but fantasy cultures that are very transparently borrowed, or "calqued" from real life cultures. Here's a quick and dirty list of some of the important ones:
Vikings: Vendels, Varangs, Norsmenn
Lapplanders and Permians: Beorms, Kvens, Veps, Iz'vataz
Eskimo: Salliqmuit, Saqqaq
Anglo-Saxons: Haestings, Marrings
Celts (Scott/Irish): Gaidhel, Gaelings, Cruithni
Byzantines: Komnenians, Helladians
Slavs: Kayazy, Leches, Wends, Surbs
Turks: Vatheks, Komans, Khozars
Eastern Woodlands "skraelings": Ojowe, Saunak, Beosuk
Confederacy of the Longhouse (Iroquois): Mowauk, Kehaka, Wendat
Chinese: Fusangites, Tsin, Tsi
Plains indians: Tatankans, Nakota, Komantsi
Cliff dwellers: Kayenta, Azani
Mound-builders, Mississippians: Cahokians, Chumaws, Cherkash
Atlanteans: mixed with some native americans to form classic moundbuilder culture in the American south
Muans: refugees from a shrinking Zealandia colony; Ainu, Spirit Cave mummy and Kennewick man
Lemurians: refugees from a shrinking Kerguelen--unlikely to appear in significant numbers in Europe or North America