>Well, Arizona and New Mexico are both Democratic states,
Huh? Not that Democratic means much but you're the one who brought it up:
http://en.wikipedia.org/wiki/Arizona#Current_elected_officials
Since the election of Dwight D. Eisenhower in 1952, however,[Arizona] has voted consistently Republican in national politics, with the Republican candidate carrying the state every time with the sole exception of Bill Clinton in United States presidential election, 1996. In recent years, the Republican Party has also dominated Arizona politics in general. The fast-growing Phoenix and Tucson suburbs became increasingly friendly to Republicans from the 1950s onward. During this time, many "Pinto Democrats," or conservative Democrats from rural areas, became increasingly willing to support Republicans at the state and national level. However, the previous Governor of Arizona, Janet Napolitano is a Democrat; she was handily reelected in 2006.
On March 4, 2008, John McCain effectively clinched the Republican nomination for 2008, becoming the first presidential nominee from the state since Barry Goldwater in 1964.
See also: United States presidential election, 2004, in Arizona
Arizona politics are dominated by a longstanding rivalry between its two largest counties, Maricopa County and Pima County--home to Phoenix and Tucson. The two counties have almost 80 percent of the state's population and cast almost three-fourths of the state's vote. They also elect a substantial majority of the state legislature.
Maricopa County is home to almost 60 percent of the state's population, and most of the state's elected officials live there. It has voted Republican in every presidential election since 1948. This includes the 1964 run of native son Barry Goldwater; he wouldn't have even carried his own state had it not been for a 20,000-vote margin in Maricopa County. Similarly, while McCain won Arizona by eight percentage points in 2008, the margin would have likely been far closer if not for a 130,000-vote margin in Maricopa County.
In contrast, Pima County, home to Tucson, and most of southern Arizona has historically been more Democratic. While Tucson's suburbs lean Republican, they hold to a somewhat more moderate brand of Republicanism than is common in the Phoenix area.