I mentioned a couple days ago over on FB that after seeing Avatar I found it unlikely that the Na'vi were native to Pandora. I still hold that this is a valid assertion, given the information we have from the movie, but that it could use some explanation. I also recognize that, not having read the novelization, Cameron may have already reconciled some of the issues I raise here.
I think that it is something endemic to parenting, or perhaps simply unique to my own family's habits, that when presented with the overly simplistic stories told to children we attempt to add complexity and depth. We find ourselves doing this even for adult stories that are simplistic, such as James Cameron's Avatar. This is not to say that the movie was not good, I think that the ticket price was well spent, but that the story is one that is simple and well-known to most American moviegoers.
Because of that simplicity I found myself looking for more from the world, once the credits had rolled. The first thought I had, as I trekked across the icy parking lot was that the Na'vi, as shown, were probably not native to Pandora. There are a number of anatomical clues that suggest this:
1) Two-Eyes: The majority of Pandoran fauna shown have four or more eyes. From the Great Leonopteryx to the Hammerhead Titanothere to the dimunitive viperwolf, most of the animals on Pandora possess more than two eyes. Indeed, the only animals that seem not to share this trait are those closely associated with the Na'vi such as the Direhorse or the Mountain Banshee.
2) Four Limbs: Even more telling than eyes is the number of limbs found on Pandoran animals. Without exception, all save the Na'vi possess six limbs. Some show signs of limb atrophy, such as the Protolemuris, with a single upper arm and a bifurcated forearm, but the Na'vi show no signs of even vestigal limbs.
3) Respiration: The Na'vi breathe through their mouths and noses, just as humans do. All other creatures we see on Pandora have spiracles on their chests for respiration. While it is possible for such drastic changes to have evolved naturally (e.g. Whales and other cetaceans' blowholes), we see no direct evidence for such. Indeed, the Na'vi seem well-adapted to their environment.
4) Synaptic Uplink: While many of the animals on Pandora possess an extra, external nerve conduit, only the Na'vi are able to make use of this for cross-species control and communication. One would assume, given the totality of control the Na'vi seem to have over creatures once linked, that other animals would have evolved similar capabilities either for defense or for hunting. We do not see this, however, not even in a more rudimentary form.
Given these features, I think it likely that the evolutionary roots of the Na'vi are very different from the rest of Pandora's fauna.
One possible cause for these differences could be found if Pandora was terraformed in the distant past. If, at one time, the Na'vi were a spacefaring civilization much like the humans presented in the movie. The Na'vi would either have adapted the surface of Pandora to meet their needs, or more likely considering the divergence from local fauna, would have adapted their bodies (and nervous systems) to the planet.
In this case, some disaster long ago would have meant the destruction of the Na'vi technological base and a return to a hunter-gatherer lifestyle.
A slightly more extreme theory holds that Eywa, not the Na'vi, is the dominant life form on the planet Pandora. Given the information presented in Avatar, I believe that this is quite likely. Whether the Eywa are native to Pandora, or arrived at some time in the past we can't yet tell, but it is obvious that they are both sentient and in control of the Pandoran biosphere.
First we have the evidence that a vast network, even more complex than a human brain, exists within the Pandoran soil. This network connects all life within the rainforests, from simple plants up to the great megafauna such as Thanators and Hammerhead Titanotheres.
Second, sentience can be seen in the way that Eywa responded to Jake Sully's plea for help. Though the response was not immediate, it showed a controlling hand. The way in which the Banshees and Titanotheres not only gathered to assist the Na'vi resistance, but seemed to know what specific targets to focus on, shows intelligent action rather than random attack.
As an aside, I do not think that the Eywa have a direct, constant, sense of the world the way humans, or the Na'vi, do. The gap in time between Jake's request and the animals' response suggests that the Eywa needed to wait for information about the human threat to be gathered. At a guess, the first Na'vi and other animals who died were linked into the Eywa's network and "downloaded" to provide this information. Additional time was needed to gather the appropriate resources and to organize them.
As we have seen on Earth, intelligence and the ability to marshall resources are a stunning evolutionary advantage. Humans have displaced most other large animals, filling a huge variety of ecological niches by outcompeting the previous residents. I believe that the same would as true for sentient flora as it does for sentient fauna. Any ecosystem inhabited by an Eywa would quickly become suborned into that Eywa's own network, or would be displaced by the flora and fauna under an Eywa's control. Once one locale was filled with the Eywa, it would look for methods to expand itself into neighboring ecosystems, either by converting them or by adapting its own resources to survive in new environments.
In this scenario, the Na'vi are simply another tool of the Eywa. Providing eyes, ears, hands, and most importantly context. As semi-autonomous, the Na'vi are able to operate outside of the Eywa's direct influence, but can be trusted to return to a network node (Tree of Souls) to return the collected data. The neolithic technology of the Na'vi has been preserved because, at this point in time, that was all the Eywa needed the Na'vi to possess. With the advent of invasive species (e.g. humans), or with Pandora's biosphere filled entirely by one Eywa, the Na'vi may quickly develop technology necessary to bring the Eywa to other worlds. Indeed, given some of the information on James Cameron's own writeup of the movie's history, I think it is safe to say that there are many nascent Eywa already growing on Earth. Some as part of scientific collections, others arriving as simple, incidental, stowaways on human returnees.