It’s a wicked translation problem. Translate the names by meaning, and you make the original sound like a bigoted nineteenth-century impression of Native Americans. Worse, you give the names’ meaning too much prominence in the reader’s mind; as Baldur says, these names are names first and meanings second….
The opposite danger, though, is considering meanings—well, meaningless. If you don’t translate the name, how do you get across its echoes?
One possibility is the name-pair, the name in the original language paired with a translation…. The downside is that this is slightly misleading; it’s easy for the reader to believe that the translation is part of the name in the original…. (In an electronic edition, I would be tempted to include the translated name as a pop-up note or in a lighter text color. The latter might be possible in print also; depends on the publisher.)…
If all else fails, there’s always the footnote. In this specific case, though, I myself would prefer an annotated name glossary; it’s a darned shame to have to hunt through the entire book for the first instance of a name just to find out what it means.
Obviously, each case is different and has to be addressed on its own merits, but I wonder if readers have general thoughts on the subject? For me, this is a case where the internet has obvious benefits: a scrollover note on the name’s meaning would be unobtrusive in a way that can’t be matched in print. (Personally, there are few things I love better than an annotated glossary, but I recognize that it’s a love not shared by the majority.)