Did you have the same reaction in 3e with Extraordinary abilities? Because Ex abilities are exactly the same as Martial powers. They are not inherently magical (can't be dispelled, work in an anti-magic zone) but they are certainly not normal either.
I treat Martial powers in the same way. Ex abilities allowed my monk to effectively Feather Fall, dodge fireballs, be immune to diseases, and actually granted me spell resistance and speak to any living creature. Somehow my training as a monk, completely non magical, renders me immune to magic and allows me to automatically communicate with anything in the universe.
To me, there isn't a huge difference here between 3.5's Ex abilities and 4e's Martial powers.
And, let's be honest here, the Supernatural abilities were just a patch to allow certain types of casters to bypass spell resistance.
I've never really gotten why people have such a difficult time swallowing a fighter having powers and yet never, ever complained about, say, a monk, doing the exact same thing.
Actually, I did have a bit of a problem with Extraordinary Abilities as well. There was magic, there was supernatural, there was extraordinary, and there was mundane. I never really understood why extraordinary and supernatural couldn't be the same category.
I have no problem with a supernatural power source. As an example, I consider the Primal power source to be a supernatural power source, not a natural power source (the Martial power source should be a natural power source). The ability to change yourself into a tree or an animal is "outside the laws of nature", hence, supernatural.
I do think that the power sources should be clearly defined and the Martial power source should be the "mundane" one. No healing. No teleport. No flying. Especially at heroic levels. But, the ability to kick the snot out of the bad guys with just a simple weapon. That should be the strength of the Martial power source. MARTIAL. Hit point damage on a heavier scale compare to the other power sources. But, very little in the way of effects. And the effects that do occur should be martial-like. For example, knocking a foe prone, shifting, and at higher levels, stunning a foe. But not giving buffs to allies and not giving heals to allies.
A Warlock or other Arcane or Psionic should not be able to damage foes like a Martial PC can. The Warlock should be throwing out effects more than the Martial PC can, but hit point damage should be the realm of the Martial classes. Effects should be more the realm of other Power sources.
The Arcane power source should be good at throwing out elemental effects and illusions and many other "magical effects".
The Divine power source should be good at throwing out buffs and debuffs. The gods should be assisting, not directly throwing out the mega hit point damage and mega effects.
The Psionic power source should be good at mind games and telekinesis.
And virtually no power source should be handing out teleport at low levels. Just like virtually no power source should be handing out fly or invisibility at low levels.
The power sources should open up a bit at Paragon level. The Martial characters at those levels can do the Wuxia type stuff a bit. Great leaps, hiding in shadows better, etc. But still no teleporting. At Epic, it becomes demi-god like. Still martial in tone, but able to do things that no normal man can do.
I'm ok with that.
I just have an issue with things like the Original Come and Get It that came straight out of acquiring aggro out of an MMORPG.
Supernatural taunting isn't martial. Sure, you could probably introduce it at mid-paragon, but it's game mechanics driving flavor, not the other way around.
By the way, I think that the "role" concept is what messed a lot of this up. We HAVE to have a Martial Leader who can heal like every other leader. We have to have a Martial Controller.
No. The game doesn't have to have those things. These are artificial metagame concepts that took over. Again, the game mechanics driving instead of the flavor driving.
Power sources are flavor. The flavor should be the motivating idea behind the game design because then narrative and game mechanics do not clash as often. The game mechanics should be there to allow the narrative to work, not the other way around.
Seriously. Magic isn't magic when every PC can do it. The flavor of magic is gone when every power source can do nearly every type of effect in the game system. Each power source should have clearly defined strengths and clearly defined effects that just cannot be done in the power source.