Native Americans were given a pretty raw deal. Given the option of being made vassal states of an expansionistic, conquering power, they took it. And they've been vassal states to their detriment ever since.
Giving NAs the same representation in the American government that is enjoyed by actual American citizens is a non-starter, for what should be obvious reasons. L.Y.S.'s proposal is functionally equivalent to giving Canadians or Mexicans (or Palestinians) representation in Congress. They're not citizens, it's not their country, they're not entitled to that privilege. It is not the appropriate means of redress.
I agree with L.Y.S. that the current NA "twilight zone" status is untenable. One way or another, it should be ended. I see two ways of doing this:
One way is that, like Kosovo, the Palestinian Authority, and others, they forcefully press for full recognition as independent nation-states, with all the privileges that implies, free to make their own way in the world as best they can with the resources available to them and the international relations they are able to foster. That's the way it is for every other nation, why not the "first nations"?
The other way is to simply dissolve the separate "sovreign" enclaves, and become American citizens. Then they get the same privileges of representation as every other American citizen.