Chaco is a premier dark skies park and often visited by the Albuquerque Astronomy Club. Don't miss it, but don't take the RV because one part of the road is terrible (the part through a corner of the Navajo Reservation).
We have also stayed at Santa Fe Skies and Taos Valley rv parks, but much prefer Lake Cochiti and Abiquiu Lake, which are both COE campgrounds (1/2 price with Fed Sr. pass). Heron Lake SP, mentioned earlier, is one of our favorite NM state parks. We have stayed multiple times at Sugarite Canyon SP near Raton and at least once at many others. Can't beat $14 for W/E sites and $18 for FHU sites including daily park pass, dump, and heated shower rooms.
Others have mentioned spring winds. I saw a blown-over semi blocking both lanes of I-25 at Las Vegas, NM, and I-40 closed at the NM-AZ border for two days due to high wind warning. Gallup was so full of truckers that every motel had no vacancy signs by noon! Both wind events were in April, as was a snowstorm on I-40 in the Sandias just east of Albuquerque. Spring in most of the Rockies comes in May more often than April!