I spent a few years in NM (many years ago!) for college -- I think Colorado mexican food is pretty close to my memories of New Mexican Mexican food... and no - I don't think you'll find much like that here.
El Rancho Grande (its a chain, there are several locations) is all right for what you get around here, but I don't think its what you're looking for.
You will get used to the differences eventually, and appreciate the good places you find around here - even though they're different that what you expect. But you'll always crave a little bit the food from Colorado. Just makes vacations/trips back that much better.
Me. I'd kill for a grilled steak with mild green chile grilled on top, with some real tortilla soup with avacado slices on top, with light and crispy sopapillas on top. In a pinch I'll take Indian Fry bread instead...
but so far.. nothing like that round here. My tastes run more to the SouthWestern than the true Mexican, but I ate in enough Mexican dives in Las Cruces to know the type of food you're describing. Just haven't found it back in the midwest. Have found other tasty places, but just not the same.
Viva la difference!
good luck in your search!