A minor point, but I'm more comfortable using the term "Indians" since I was reminded that there was no nation called "India" in Columbus's time, and Europeans used the term "Indian" for anybody who lived east of the Indus River. Columbus thought he'd reached Asia, so it was perfectly reasonable that the people he met would be "Indians". The term stuck, and the people who came after haven't been able to come up with a catchy alternative that's been widely adopted.

In Canada, the term "First Nations" is gaining popularity, and to me is less ambiguous than "Native" (since, as someone above pointed out, anyone who was born here is a "native"). The French term "nations authochthones" is a neat phrase, but the English word "autochtonic" might be a bit cumbersome for some...