It's possbible to cover even mountenous terain with cell phone coverage, here in Switzerland, they've managed to cover almost 90% of our (small) country, including 10000ft mountains with cell phone coverage. Cell phones are widely used here, an unexpecting guest from overseas might even think we're cellphone crazy in Europe. It will cost a lot of $$$ to cover remote locations like Cumbres Pass completely, but one large antenna on Cumbres Pass might do the job, to cover the C&TS, severall small antennas would be needed in places like Toltec Gorge.
I think upgrading the radio system with one or two relay stations is the cheaper way to improve the situation.
Boris