base871 wrote:We got the permits, but the local hearders said "No way in hell". So now we cant cross their "land" to get to the trailhead. Sucks. That place was amazing!

I'm a recent transplant to the Navajo Nation (Tuba City area), and have a little more information for people to consider. I'm a lawyer who lives/works on the rez, so that's the perspective from which I'll add my two cents:
I've been told that there are around a DOZEN different land statuses on the reservation. To name a few: Most of the land commonly known as "reservation" is land owned by the U.S. government, and held "in trust" for the benefit of the tribe. There are also farming allotments, which are also owned by the U.S. government, but are held "in trust" for the benefit of the "alottee," or recipient of the allotment. There is also "fee land" (that's an archaic use of the word "fee,"
not referring to anything monetary). An example of fee land is the Big Boquillas Ranch 80 miles west of Flagstaff, which was "regular" land (as you probably imagine it) that could have been purchased by you or me -- it just so happened that the Navajo Nation put up the cash and bought the land for itself. There are also "home site leases," "business site leases," and "grazing permits," which grant only a USE Right and not a possession/ownership right. Interestingly, however, many traditional Navajo families will refer to grazing land as "my family's land" -- perhaps due to confusion regarding the concept of use vs. possession, and perhaps because there is a fundamental (unwritten) Navajo law concept of "customary use," which can murkify things further (yes, I made up the word "murkify"). There are also lands that have been disputed between the Navajos and Hopis for decades, some of which have been recently settled.
I'm giving this information partly as a matter of practical assistance to the hikers here, and partly as a reminder of cultural sensitivity when using Indian land. In American culture, we like things to be clear. That's why we have lawyers -- to help disputes reach a point of finality. In a nearly 200-year-old U.S. Supreme Court decision called Johnson v. M'Intosh (
http://en.wikipedia.org/wiki/Johnson_v._M%27Intosh), the U.S. Supreme Court decided that Indians didn't hold legal title to the land they occupied. This decision also helped create the "discovery doctrine,"
http://en.wikipedia.org/wiki/Discovery_doctrine is basically regarded as the excuse that American courts made up for taking land away from the Native Americans. If you go to law school, you'll take a Real Property class in your first year, and this case will probably be the first case in your textbook, since it lays the foundation for all future U.S. land transactions.
To revisit the line I quoted above (from HAZ user base871), on one hand a sheepherder might ask you to leave his land even though he only has a right to
use the land and therefore no right to
exclude people from the land; that's the view under American law and culture. But on the other hand, Navajo fundamental/traditional law is very real in Navajo culture. (Only recently was Navajo fundamental law -- i.e. unwritten customs-- incorporated into the Navajo law/statute books.) The bottom line is that Indian land is "sovereign," allowing them to make their own laws, written or unwritten. The U.S.A. imposed a right to intervene many many years ago, but especially in recent decades, the U.S. government is giving the tribes more and more independence.
This might not actually answer the underlying question of whether, when, and where you can hike in Coalmine Canyon or elsewhere on the reservation, but if you're dedicated enough to really try to find the "right" way to hike here without cramping anybody's style, hopefully this at least gives you a little more perspective. I would actually love to hike Coalmine Canyon as well, and if I ever find the time, I'll probably try to do some investigating myself and let you all know what I find in terms of an arrangement that satisfies the local people and the tribal government. Just remember that if you try to fly under the radar and hike areas where you perhaps shouldn't be, that's going to make it harder for other folks to negotiate the privilege to go there with the blessing of the local people and governments. Whether it's hikers, hunters, auto mechanics, lawyers, or politicians, we all know that somebody who breaks the rules and gets busted is going to ruin the image of a lot of other people who try to do things the right way.
[Stepping down from soapbox.] I definitely don't want to sound fatherly or preachy, but I've learned a lot about Navajo culture even in my ~6 months living/working here, and wanted to share my insight for the benefit of other HAZ folks.