I too taught on the res for 10 years, 15 years ago. At the time I left, there were transitions with some schools, like Dzilth-Na-O-Dith-Hle, moving from BIA to grant or contract schools, with the Navajo communities taking over local control. One of my anglo teacher friends lost her job during the transition although she had been with BIA 15 years. Another friend relocated to teach with GMCS (Gallop-McKinley) to be closer to civilization. The salaries went down for some that transitioned from BIA to grant/contract.
I'm looking at the BIA pay scale from a few years ago & it looks pretty good, especially since past BIA experience+educational level would push one up the scale:
http://www.bie.edu/cs/groups/xbie/do.../idc010676.pdf
According to that, I'd be making way over 100K if I had stayed. However, the isolation, winds, & constant tumbleweeds got to us LOL
Good luck to you!