If you combine complexity (think of chess) with fast reaction times (think of realtime combat), then you will have a very low frustration threshold.
It's really not that complex. The way I'm reasoning it, the player would get into a battle, drain their stamina, and burn some HP. Supposing the UI isn't terrible, they will realize what they're doing and form a heuristic to deal with it; namely, keep stamina low, but not empty. If the game is as fast as Quake, this could be a problem, but if it's a bit more tactical (like EVE Online, to use DI2agon's example) the player has more time to think about... well, tactics.
Turning to DI2agon, the universal rule of game design applies here: make a quick-and-dirty prototype, and see for yourself if it works. Like in science, talking about how it would be will get you so far, but you're not really a scientist until you test your hypothesis.
Honestly, what I'm more concerned about is that this system isn't complex enough. If magic, melee, and ranged attacks all drain stamina, then what differentiates magical attacks from the mundane, apart from cool particle effects? As for the setting, a fantasy universe with godlike beings who have sufficiently advanced tech is a great idea, but how would you get across to the players that it isn't magical to them?