New Mexico: 2004 (Bush managed to win that has been a strongly Dem state since 1992 due to overperformance among Hispanics.)
New Mexico was by no means solidly Democratic in 2004. In fact, it was still a very good bellwether state at that time, even voting slightly more Republican than the nation in 1996/2000.
NM may have been the best bellwether state in turns of margin until 2008. Ohio seems to be its main competitor there, but boy did Ohio blow 2016.
While NM flipped R in 2004, it voted more R than the nation in 2000 and more D than the nation in 2004.