I'm going to focus more on New Mexico here, because I think that the explanation for Colorado (save for a few southern counties that are culturally much more similar to northern New Mexico than the rest of Colorado) is urbanization, as stated in the other answers.
To summarize
The first thing to note is that if you flick through a couple of county-by-county presidential election maps, you'll see that the north-central counties of Taos, Rio Arriba, Santa Fe, Mora, and San Miguel often vote the same way. This region is responsible for a lot of the cultural identity of New Mexico, and have strongly influenced the structure of its government. The political views of these counties have also started to line up with more urban counties like Dona Ana, Bernalillo, and Sandoval as urban areas have become steadily more blue throughout the 21st century. This political alignment between the cultural and population centers of New Mexico has led to it becoming decidedly bluer than many of the surrounding states, where an area as rural as Northern NM would almost assuredly be overwhelmingly conservative and might offset the liberal lean of the urban areas.
A history of northern New Mexico
It's worth taking a closer look at the history of this, since it's interesting and rarely discussed outside of New Mexico. The thing that makes north-central New Mexico different from a lot of the other western interior states is a culture that is much older and distinct from the other states in that category, due to the history of how it was colonized. To greatly generalize, after the introduction of horses to North America but pre 1800s, much of the western US consisted of very sparse Spanish presence and indigenous populations that were either small and disorganized or very mobile and nomadic. This meant that by the time the treaty of Guadalupe Hidalgo rolled around in 1848 and westward expansion began in earnest, Anglo Americans quickly took political control of these areas and were able to leverage the newfound industrial capacity of the US to slowly but surely consolidate the once spread out native tribes into a small collection of reservations in areas less desirable for settlers.
This story was not the case in north central New Mexico when the Spanish first arrived in the late 1500s. The natives in this region lived in organized towns and practiced agriculture, similar to the arriving Spaniards and often more efficiently since they were used to the climate. This fact, combined with the isolation of the area, lack of natural resources to justify a heavy presence, lesser industrial capacity and technology to fuel a war, and a decisive coordinated revolt meant that the Spanish were never able to establish a successful mission system to convert natives like they had in California. Eventually, they more or less gave up on the goal of converting the natives to Christianity, and instead focused on settling the areas not claimed by the natives.
The focus on settlement rather than evangelism left New Mexico with a much stronger
Spanish culture and population than other lands ceded in the Treaty of Guadalupe Hidalgo-- New Mexico's Spanish speaking population in 1848 was around 4 times the combined Spanish speaking population at the same time of what is now Arizona, Texas, California, and Colorado. Keep in mind that San Juan in Rio Arriba county was founded in 1598 and Taos pueblo around 1000-- by the time New Mexico became a territory of the US, even the Spanish settlements were as old as the US is today. Although the percentage of New Mexico's Hispanic population did drop drastically by statehood due to an influx of Anglo homesteaders, the strong culture and higher Hispanic population present meant that Spanish language and heritage was protected more than in other states, and that Hispanics received more political representation than they did in other western states during the 20th century.