If Klaus Schmidt was correct and the oldest of the structures he unearthed at gobekli tepe were the best constructed and were created just after the first melt pulse at the end glaciation. Then, it seems most likely that they were constructed in commemoration/(memory?) of things past. (During the recent glaciation and perhaps the lgm?) and then (one wonders) What things?
A few hundred years is enough time to have developed a new and quite different way of life, including considerable complexity. Lewis and Clark bought horses from Reds whose entire way of life - including religious ritual, basic economic exchange and cultural or diplomatic structure, domestic technology, and patterns of travel and residence - revolved around these animals. That would have been maybe 250 years, at most, since the first horses were stolen by completely different tribal Red people from the Spanish colonial herds in Mexico, a thousand miles away.
The First Nations that were moved wholesale from one area to another had to react to the new conditions or die. "Uncle" Sam didn't care. Climatological changes, geographic changes, etc., were met and we learned, or died. Humans are good at adapting.
Some of the cultures (such as the Northern Cheyenne, described by early White observers as the finest light cavalry on the planet in the mid 18th century and by modern researchers as possibly the physically healthiest human beings on earth at that time - this would be after the Great Death of first contact, and before the cholera etc of the mid 19th) had developed their new ways of life - complete with religions and rituals and specialized technology and established economies and so forth - within a generation, and in at least partly "voluntary" relocations (under military pressure, but from traditional enemies). Some (such as the Mandan) changed without wholesale relocating - from rectangular to circular lodges, say, and other aspects that would leave durable archeological evidence. So it can happen fast, and in place. It's a possibility.
Ironically, parts of the US Constitution were copied from the laws of the 5 nation Iroquois Confederacy. http://native.wikia.com/wiki/Iroquois_Confederacy