You are looking at their perceptions from the perceptions of our levels of technology. You're not looking at it in the sense that a culture from such an un-advanced level would look at something. There are multiple accounts of relatively less technologically advanced cultures that would calssify things like armor plating and metal swords as things of "magic" or explained via terms they knew. "Silver skin, hard as rock, impenetrable by arrow." "Big roaring bull, skin of blackened rock, on metal colored path" (train).
Human mythology is not simply based out of religion, or there being some higher power. Human mythology is the explanation of what they dont understand by using things that would make sense to them. Thus, in essence, making sense of the things that don't. The Na'vi showed all the tell tale signs of that. They revere Eywa as their Deity. She is made up of all living things, is the line, but do the Na'vi conceptually understand that? I seriously doubt they can understand that Eywa literally is the combination of everything on Pandora. They will see it more as a meta-physical principle, kind of like the explanation of the force in Star Wars IV. "It surrounds us, binds us, and penetrates us." Mysterious in nature, harassed as a power, but not fully understood.
Yeah they can look at the fan lizards and the many ikrans and see some similarities, but I'm pretty sure before the school was around, and right at the first meeting of RDA/Na'vi, the Na'vi were like, "wtf is all this?" Calling the humans as little creatures wearing a mask of water, because of its reflective qualities. Calling the helicopters and winged beasts, making the noise of many devil bees, bearing the teeth of the largest Ikra (painted teeths) spouting out fire and smoke. etc etc. People on earth, indigenous tribe explained flying craft as dragons making wide noises and spouting out flame and fire. And they experienced things like birds and other fouls.
And to expound on the fact/theory thing, Science is observation. Fact is defined as what is perceived to be "true". But perceptions change all the time. It was scientific fact to think the Earth was round. It was scientific fact the think that the Earth was the center of the universe. It was also scientific fact to think that bloodletting kill the plague. Yet the perception of the scientists change so often, that was may be fact now, may not be fact in the future. Even now we are on the verge of finding out that the speed of light is no longer the universe's speed limit, but that the speed of light just is. The Scientific method only shows consistency in certain observations. But if one can fin inconsistency, then that particular science is no longer fact, but flawed. It is no longer law, but theorem. Or it is no longer theorem, but falsified theory.
The stuff that scientists and science perceives is already happening around us. Yet, even in our advanced society, we still are only able to perceive the universe in what limits we currently have to our perception. You ma say we dont have limits, but I cant guarantee that if we do actually discover that one can truly go faster than the speed of light, the way we perceive things today can and will most definitely change. Science, as it stands, should almost never be considered law. Because it is always shifting.
EDIT: I should note that I am not discrediting science at all, calling it false or heretical. I'm just saying that what science is now, may not be.