It's crazy seeing Reserve, NM mentioned on HN! What you experienced is so common around here, I encounter travelers a few times a year in the Gila NF that need assistance after following their GPS nav on the "scenic route" ...most are calm, some are in panic mode and happy to see someone.
Did you happen to follow a road in to the Acoma reservation in the El Malpais?