--Most of his companions would only be like in their 40s or 50s. Hardly retirement age for politicians 
The thing is, we have strictly no idea of how things went before, during and after the Ghost Dance War.
What did happen to the original leadership of the SAIM? Were they arrested in the 2009-2011? If so, chances are the US authorities would put them into maximum security prisons and not just in the internment camps. After escaping from the Abilene camps, did Coleman use his magical powers to free them, or rather took advantage of their absence to take control. Did he put the same guy back in the leadership positions, or did he replace them with the most loyal, or those with the most strategic skills, or the most magically powerful? How old were they? Somewhat significant, since culturally, most tribes tend to value the elders. Did all the tribes instantly put all their faith in those who had magic powers?
Coleman is called a hero because he won the war, but you have to remember he first was a hardliner, calling for all non-Amerindian to leave North America, first alienating the most soft-spoken ones who only wanted freedom and keeping the mining corporations out of their lands. Then he signed the Treaty of Denver, he accepted reclaiming only half of North America, this time alienating the hardliners. The companions Coleman chose when he had to fought a war maybe did not share all his views on the peace negotiations, let alone society matters or economical issues.
For the following decades, almost all politicians in the NAN would be veterans. Actually, it would probably be difficult to have a career if you weren't one. I'm pretty sure a lot of them would actually try to paint themselves as one of Howling Coyote's companions.
Basically, it's the same thing that happened in every country that fought a liberation war. And where democracy works, you see that no matter the age at which you started, staying in charge for more than three decades is very rare. Too many voters resent you for something you'd have done at some point.
In the NAN, and more specifically in the Salish-Shidhe Council, I would hazard that the politicians who came up with the idea to fully open the border to elves, dwarfs, orks and trolls and allow them to create their own tribe, had something of career turning point when the Cenesté tribe seceded, taking a third of the territory with them, and dozen of council border guards were killed by a bunch of teenage elven insurgents.
It maybe would actually make more sense that the old leaders that fought alongside Coleman and were in charge in the Salish-Shidhe Council between 2018 and 2036 were rather more into
realpolitik and sympathetic enough to corporations, jumpstarting the SSC biotech industry and willing to open the border to metahuman labor force. It's the new generation who replaced them when they got ousted for the Cenesté debacle who either accepted or refused the BRA.