Recently I've been thinking about finalizing names, and Lands of the Barbarian Kings really was mostly a working title to remind me what the essential elements of the setting are supposed to be. After all, you can't really call them barbarians when these people are the most civilized cultures that ever existed in the world.
And actually, I think the original name still seems quite appropriate and sufficiently snappy: The Ancient Lands. The world is very old with a very great amount of prehistory, but it is also still quite wild and primitive. I don't think I'll ever come up with anything better, especially as there is already a setting named Wilderland.

I have about 40 ideas for settlements for which I have decided where to put them and what they are about, and since the best ideas appear when you write things down, here they are.

Ancient Lands Settlements

Cities and Towns of the Far North
Clansmeet: (Town, 9,000 kaas) This large town lies in the center of the plains that are the homeland of the kaas, in the very Northwest of the Ancient Lands. Despite its size, it lacks any walls or wooden pallisades, as building material is scarce, and none of the clans could ever gather enough warriors to challenge the towns defenders. It is only surrounded by a wide ditch that is impassable for carts or pack animals carrying loads. No single clan controls the town, but its council of elders is entirely dominated by the three largest and most powerful clans of the area. The town is a major center of trade and a vital part for the survivial of all the plains clans. Without the trade comming through its markets, most villages could not survives and the plains inhabitants be forces to return to an entirely nomadic life like their ancestors of ancient times.
Whitemount: (Town, 8,000 elves)In the hills that seperate the Witchfens from the lands of the kaas lies the largest elven settlement in the Northlands. Located between three low peaks, it overlooks the Witchfens to the East and offers a clear view for miles. The town is almost entirely made out of white stone and protected by stone walls, which make it appear more like a small city than one of the farming towns of low, half-burried huts, that are the most common the Northlands. To people from the large towns and cities of the Central Lands, Whitemount is known as the only island of civilization beyond the edges of the large forests that dominate the Ancient Lands.
Mountain Fortress: (Town, 6,000 kaas) This massive fortress is located high up in the mountains that define the northern borders of the Ancient Lands. It is the home of an entire clan of kaas, who control the surrounding lands for several days of travel and who are widely considered to be the greatest warriors of the Northlands.
Ice Sea Port: (Town, 5,000 arctic humans) Where the path that leads through the northern mountains ends at the shores of the northern arctic sea, the semi-nomadic human clans have build their largest settlement. With the tundra being a soggy bog for large parts of the year, transport between the villages is mostly done with longboats and kayaks along the coast, and this port town is the only one that has a road that leads to the southern lands. Basically all gods that enter or leave the tundra pass through this town.
Witch Hill: (Town, 3,000 fen humans) Near the center of the Witchfens, not far from the road that leads from the pass through the Northern Mountains to the southern lands, is one of the major centers of the elusive human savages of the Fens. The town lies at the foot of a prominent hill, that is one of the main ritual sites of the witches that govern their society, from which it gets its name. While the humans have few contact with other people, it is assumed that the witches of Witch Hill are either the official leaders of their religion, or at least carry significant inofficial authority. There are few visitors to the town, but at least the locals do not attack strangers on sight, which seems to be the cast with a very large number of their smaller settlements.
Pass Town: (Town, 2,000 fen humans and elves) At the foot of the northern mountains and at the beginning of the trail that leads over the major pass to the arctic tundra lies a small trading town. It's economy depends entirely on traders travelling over the mountains, by supplying them with food, repairing carts and wagons, replacing lost horses, and providing local guides.
Shaman Camp: (Village, 800 kaas) In the very northernmost Border Hills, which form the western border of the Ancient Lands, is one of the main spiritual centers of the kaas. However, its shamans belong to a small minority that has dealing with the ancient spirits of the underworld and the Void beyond the worlds, which makes them highly suspicious and untrustworthy to most of their people.
Ice Lake Village: (Village, 800 arctic humans) This village is located on the banks of one of the many shallow lakes near the coast of the arctic sea. A small river connects it to the sea, which allows boats to travel to other villages in the region. There is nothing particularly special about it and it is examplary for the settlements of the local humans.
Stonespire Keep: (Village, 600 fen humans) In the northern parts of the Witchfens, about one weeks travel from Whitemount, lies an old fey tower that rises high above the surrounding lands. There is probably nobody who really knows what it's originalpurpose was, but a clan of the local human barbarians has made its home around it and inside the lower halls, and its shamans have been trying to uncover its secrets for decades.
Frozen Keep: (Village, 500 artic humans) Not far from where the mountain pass opens into the open tundra lies an ancient fortress that has been carved into the black rock of the mountains. It is the home of a group of renegade shamans who have turned to demonic magic, and their followers, who are despised by most of the local human clans.
Oakridge Village: (Village, 250 arctic humans) Unlike most settlements of the humans that are at home in the arctic tundra, this village is located high in the foothils of the mountains and the local people make their living from hunting bears and mountain goats instead of fishing and herding reindeer. Protected from the storms by steep mountain walls on either side, it is like an oasis in a frozen desert, being home to numerous ancient oaks that are rarely found on this side of the mountains.
Ranger Keep: (Village, 200 elves) In the very south of the Witchfens, just barely within sight of the edge of the great forests, lie the ruins of a small keep, hidden and protected by a group of low hills. The ruins are home to a camp of elven rangers associated with the elven settlements a few days travel to the south. They serve as their eyes beyond the edge of the forest and ocasionally clash with the witches of the fens, who are constantly keeping track of the elves activities as well.