Craig: I've never hunted coyotes in New Mexico, but if you need a hunting partner out there, I love to throw my name in the hat. Let me know, and thanks.........Brian
Craig that is a really good area for coyotes and grey fox as well a cats. The last time I checked you could hunt coyotes with any big game license or a small game license. Be careful on the fox and cats though or buy a trapping license. There is a ton of public land in the area you are talking about. The gudalupe Nat. Forrest and a lot of BLM land. Hope this helps some, The North end of the gudalupes was full of coyotes the last time I was there.
Craig I am right in the boarder land El Paso, New Mexico is about 40 miles away and DelCity is about the same, heck Del City has lots of cats and yotes, here in El Paso we have yotes, fox, a few cats large and small...
I have hunted this area a couple of time two years ago and it is loaded with fox and coyotes up close to the mountians, we had fair luck. I usually hunt to the east of the mountians between Carlsbad and Jal which has alot of coyotes and BLM land which is a nice combination. I live at Kermit and work in NM outside of Jal. I would suggest that you get some BLM maps of the area that you are going to hunt because it is a long long ways from anywhere!
Good Luck!!