More Accurate Than It Actually Knows (With an Important Caveat)
As it says, the trope is actually more accurate than one might naively expect, but with a caveat that still renders the trope exactly as misleading as it at first appears, just in a different way.
A disclaimer: The Americas is a geographically vast and culturally diverse region, though one that also shows clear cross-pollination of mythology and commonalities in fundamental beliefs across its extant. Thus, while it should not be taken as evidence of a monolithic culture, nor as 100% accurate in all cases, the generalizations made below are intended and believed to be accurate, more or less, for the continent as a whole. My greatest familiarity lies with the greater Southwest/Mesoamerican region (roughly North California to South Mexico to the Four Corners area), so most examples are derived from and most accurate to those cultures, though lighter study of the forests of South America and the far North suggests that the extension is warranted, at least in broad strokes (in general, I speculate that the difference in culture and religion across the Americas is about equivalent to that across the greater European area and the Middle East, approximately from the British isles to the Slavic countries to Iran and Afghanistan, maybe as great as the differences including the Indian subcontinent at the most).
First off, there can be no denying that for Native peoples, "magic" existed. Animals, natural phenomena, and the land itself were considered living beings, to be feared, respected, fought and bargained with. Among various Southwest groups, all animals were considered the equals to both each other and humanity, just with different strengths and weaknesses. South American folklore still commonly lists alcohol and cigars as good bribes against being eaten by monsters. Among at a minimum the Dine, aka Navajo, the difference between human and spirit tends to be little more than a greater understanding of how the world works, the acquisition of wisdom. The power of certain physical places, especially mountains or other prominent peaks, caves, rock alignments (both natural and man-made, as among the Inuit and various Californian groups) and bodies of water, especially springs, is nearly universal. Certain songs or stories told about cultural figures (like the trickster figure most widely known now as Coyote, or the equally varied "Hero Twins" found everywhere from the Mayan to the Apache, and maybe beyond) or the origins of the worlds had real power, to cause good if used right, and ill if not. Witches (also glossed as sorcerer) were a likely cause for unexpected deaths, and a good insult to throw at disliked neighbors (though not ones that were actually suspected of witchcraft, who you did not want to cross, for reason of the aforementioned "unexpected deaths"). There is flexibility of course. Some people (likely even among those practicing spiritually charged disciplines like medicine or dancing) might believe in the spirituality of the world and the origin myths more than others. But in general, nonhuman forces, and humanity's ability to manipulate and bargain with them, were just as widely believed and fundamental to existence as God and demons were to Medieval Christians, or scientific theories like the out-of-Africa human migration, evolution or quantum physics are today.
However, while magic is accepted as a given, the vast majority of Native Americans would never touch it, even with a ten foot pole, except under the most controlled of circumstances. The reason is simple: that shit be dangerous! Insanity and ill-fortune await those who mess with forces they don't fully understand, unforseen consequences could easily arise from even the most skillful uses (at least among certain groups, the greatest wisdom was knowing that while one could change the world, it wasn't worth messing with the natural order of things), and the power itself tended to be unpleasant or dangerous to acquire: attaining power often involved fasting, easily-overdosed drugs, self-mutilation, eating silt from the bottom of a pond, fornicating with dead relatives, or other actions not to be taken unless one was really serious. Even once power was acquired, it was to be treated with great care, especially by those uninitiated. Elaborate decontamination rituals were given to medicine bags that no longer had owners, or for priestly assistants whose superior never technically got born. For a metaphor, consider it like plumbing, or computers, or electrical wiring, and then apply the Doom It Yourself trope to it. The magic of the gods, spirits, world and knowledge thereof, was something fundamental, that everyone dealt with in everyday life at a superficial level, but the average person didn't mess with it beyond that, because the consequences for messing it up are so great.
As with plumbing or nuclear disposal, there are experts, a small number willing and capable of dealing with the unseen world: shamans, witches, priests (these terms are not necessarily reflective of the actual conceptual boundaries employed, but they do give a sense of the range). Those who were either born with power or were powerful enough, ambitious enough, crazy enough to seek it out. Their acceptance by and relationship to the community varied, from place to place and individual to individual (murderers and hoarders were generally frowned upon), but in all cases such figures, medicine men and priests and great men, were to be given due respect. Just like with a medical doctor, they have the potential to save or destroy in equal measure, and they really don't have to help unless they want to.
Thus the punchline: The Magical Native American trope, with its aloof figure somewhat apart from normal society, wielding great power over the fates and the natural world, actually exists in Native culture, and did long before the European colonists arrived. Just... only a minority of people, even among Native Americans, actually fit the trope, and the Americans themselves treat the Magical Native American with trepidation and a bit of sense of otherness.
( There are, admittedly, a few complications. At least among the Californian Indians, the Dine and the Aztecs, physical strength, material wealth and social influence were considered to be evidence of spiritual power. Thus, any leadership figure was in a certain sense in possess of power. Despite this, shamans and general leaders were often considered two sorts of people. Why this is I'm not entirely sure. Possibly the power represented by luck and providence and skill was of a more "natural" form than the shamanic power, which so often involved breaking taboos and barriers, between life and death, the natural and the controlled, and so was in a sense safer. Perhaps it was a matter of degree rather than kind: as hinted at earlier, the Dine traditionally consider the difference between man and god to be a matter of accumulated power, not in fundamental aspect, and there are stories of people who acquired enough wisdom to Ascend to a Higher Plane of Existence. Thus, shamans would be those closer to becoming a Deity of Human Origin, and thus a bit less comfortable to be around than the merely lucky or skilled. Possibly it was just basic human hypocrisy: a person who throws great parties (the wealthy were often expected to share with the community by giving gifts or hosting important ceremonies; hoarding is one of many signs of witchcraft) or knows how to attract a following is going to be naturally trusted more than the hermit who spends all their time praying and you only visit when you're sick.
In addition, please note that despite the importance that magic plays in traditional Native experience, there is a difference between the sacred and the profane for Native Americans, even if that difference is not always obvious to an outside observer. For instance, the constructed rock-forms among the Inuit, known as Inuksuk, are built for a variety of reasons, some ritual, some merely as trail markers or mnemonics, with no spirituality intended at all. The difference between the two? "You know it when you see it." It's beyond the scope of this essay and of my knowledge to try to determine all the exact boundaries, but suffice it to say that, just as with any culture, religion plays an important but not absolute role. )
