These things are erratic.
According to Wikipedia, Arizona is approximately 30% hispanic, while New Mexico is alomst 47%, the highest in the US.
That ain’t no shit, neither.
About 8 years ago when my wife and I were finishing up our 50 by 50 mission we spent a week in Vermont. They were all over the place. I thought we had time traveled back to 1967. There were actually a few of them in a coffee house we visited bitching about “the establishment.” 
I figured these were guys that ran away to Canada to hide from the draft and just recently crossed the border.
Anyway, that easily explains to me why it’s a Democratic stronghold.
No no, the hippies part is true, too. 
The high Hispanic population in NM is certainly a major factor coloring it blue now. Moreover, the state’s sudden change can be attributed IMO to two factors:
(1) Compared to the current crop of national Republican candidates, George W. Bush did fairly well with Hispanics. Once he was off the stage, many of those Hispanic votes went to the Dems.
(2) There is also a substantial population of American Indians in the state (10%); Obama made a point of going after these voters in 2008.
I would highly recommend going through the 538 articles that break down state by state. It’s a great series and it really explains why each state falls where it does politically.
There’s an easy way to remember the Vermont and New Hampshire difference:
New Hampshire is the thorn between two roses.
Vermont and Maine being the roses, of course.