Not that it's a good comparison as the state has changed, but even the moderate Gary Johnson struggled somewhat in his re-election bid back in '98 (winning by eight points). Democrats won every other down-ballot race that year, with Johnson's being the only GOP win on the NM ticket during that cycle.
It's a mistake to call Gary Johnson a moderate. Yes, he was socially moderate, but he was very fiscally conservative, and he got a fairly good opponent.
That was back when Republicans were still doing OK-ish in New Mexico. Bush even won the state once with his triangulation on immigration. Without a candidate who can triangulate like that, New Mexico is definitely a task.
