The Uto-Aztecian peoples of the Great Basin at the time of first contact with Europeans (in Western Colorado, the Utes) arrived in the Great Basin and one of three separate Uto-Aztecian peoples with distinct language from Eastern California Valleys in a fairly rapid migration around 1000 CE, which is about the same time as the Na-Dene migration from the Pacific Northwest to the American Southwest.
They replaced the Fremont people who had an ethnic affinity with the modern Hopi Indians (see also here and here).
A combination of linguistic evidence, ethnography, oral histories, genetic evidence (which shows the discontinuity between earlier remains and modern Native American populations in the region), and the archaelogical evidence seem to support this account.
The best guess at the reason for the shift is that the big game oriented hunting of the Fremont lost effectiveness as a way to make a living there relative to the smaller animal and seed based subsistence of the Uto-Aztecians. Climate, of course, is also always a serious suspect in this kind of transition, particularly since it involved three parallel migrations of Uto-Aztecians and another parallel Na-Dene migration (probably actually more than one of these migrations as well) rather than just a single migrating group - disfavoring "great men of history" or "single decisive event" type explanations.
A key take away point is that the notion that North American prehistory was relatively static is increasingly being discredited as we learn more. The relatively recent mass folk migrations so familar from old school European history and from other Old World prehistory reconstructions with linguistics and archaeology also characterize North American prehistory. We are starting to be able to fill in some of the big waves of migration and replacement, large scale archaeolgical cultures that rose and fell with hints at the causes, and links between successive prehistoric cultures in the New World as well as the old. In short, North American prehistory is starting to look more like a historical account and less like a vague prologe to the eras we understand from historical records.