I'm not a huge fan of the natives either. I read somewhere though that their look was heavily drawn from actual natives that Jackson saw in National Geographic or something. One thing that can be tried is simply cutting most of the closeups of the natives. I think the witch woman and maybe the kid can be kept, but cutting most of the closeups may help. They'll still be in the film, just not so freakish.