Basically, I think that in a game type where resources and weaponry and such have to be found/gathered, having magic spells to upgrade weapons, grant temporary bonuses, or perhaps summon resources or weapons would be very cool. Of course, normally, this would be done via a simplistic magic system in which certain players have some sort of magic pool and they click a button to cast x spell. My idea is that people be required to actually make things in order to perform magic. Like some games which have gesture-based magic, this is structure-based magic. With this, people would have to make circles out of a certain substance on the ground, or perhaps special symbols, or maybe even have to have certain things arranged around them such as candles, other players, or, say, CORPSES. (Would love to see people actually have to arrange a ring of bodies to perform spectacular deathly magics.) The structures would either have one-time effects (such as summoning something), then disappear, or maybe impart lasting effects, or maybe give the wizard using them the ability to cast a spell at will later.
I doubt something like this would be implemented into the core game due to its complexity, since Minecraft seems to be headed toward a very broad, simplistic finished version, so this would be perfect for people who want to write Lua mods for Minecraft.