What is the medium that allows magnetic fields *or any forcefield* to exist? Magnetic fields are obvious distortions.. of.. something, but what exactly are they distortions of?  Massive objects produce curvatures/gradients in space-time resulting in what we observe as gravity.. what is the equivalent explanation for magnetic/electric fields?
 A: I think that the answer depends on which type of physicist you ask.  First, if you Lorentz transform the ether, then you would expect the Michelson-Morley result and that would not by itself rule out an "ether". Condensed matter physicists have theories about a medium
called a spin net liquid and Xiao-Gang Wen (M.I.T) thinks that the vacuum is a quantum liquid of string nets.
I don't know much condensed matter physics, but this looks interesting. He has posted the introduction of his book, Quantum Field Theory of Many Body Systems. Wen studied string theory at Princeton with Ed Witten and then changed fields to condensed matter theory. I don't know enough to make intelligent comments about this theory, but perhaps some string or condensed matter theorists will. This seems to provide the medium you are asking about. I put this answer out there more as what is being suggested by spin networks approach. 
A: Well, one should maybe separate the idea of "ether"  from the vacuum of field theory. The vacuum of field theory is there and fields move over it with the appropriate  creation and annihilation operators, but it is a relative frame . So if somebody really wants to hang on to a "medium" picture one can have the vacuum. It just does not have the properties assigned to ether: a universal rest frame. 
A: Ahem, “conclusive disproof” is perhaps too strong. I think it's worth pointing out that the reason I wouldn't say you've asked a "good question" is that your question seems not to have focused on the general understanding amongst Physicists that Michelson-Morlety was conclusive. The conventional position is that there is no aether. To question this is possible, but it has to be done with care, and, significantly, no-one has managed to make an argument for why it might be helpful when doing Physics to think and do mathematics in terms of an aether. One has to say, for example, that to be compatible with experiment the equations of motion of the aether and of everything else must be Lorentz invariant to quite a high degree of accuracy. That would seem awkward to classical physicists of the late 19th Century, but the advent of liquid Helium experiments makes such an idea seem at least somewhat more commonplace. Grigori Volovich, for example, has constructed a fairly extended discussion of this analogy (published by OUP, a final draft is available here). [I haven't looked at the book cited by Gordon, but his description makes it sound comparable, albeit not similar.] Harvey Brown has a fairly detailed discussion that takes a comparable point of view from the philosophical side in "Physical Relativity. Space-time structure from a dynamical perspective (Oxford University Press), 2005", although this is an entirely classical discussion.
The other problem is, as always, how to accommodate quantum mechanics, and quantum field theory in particular. That's much more difficult. The Helium example is certainly not enough to support talking about an analogous aether without far more care than anyone has so far managed to put together in one place (no-one has come very close at all).
Your secondary question, "Massive objects produce curvatures/gradients in space-time resulting in what we observe as gravity.. what is the equivalent explanation for magnetic/electric fields?", does point, loosely, to a mathematical relationship that is much more often given houseroom by Physicists. That is, GR can be constructed in terms of the mathematics of connections, and so can electromagnetism. This response is, however, at a rather different level from the way in which you have phrased your primary question, and, as just noted, the details of quantum field theory really gets in the way of any simple understanding.
All that said, with apologies for being so direct, WELCOME to Physics SE! I've learned a lot that would have taken me much longer to learn in other contexts, and I hope you have as good an experience.
A: The short answer is nothing at all - fields are a fundamental part of the universe. 
What dmckee is teasing you about in the comments is that your intuition saying that there must be a luminiferous aether, which is an idea that was actually conclusively disproven in the late 19th century by Michelson and Morley in one of the most famous experiments of all time. The fact that fields don't need to be permeating through any material was very disturbing to physicists at the time, because it seems so intuitively bizarre, but that's the way it is - fields just are. They don't exist "in" or "through" anything.
Some famous physicist - Gell-Mann or someone like that - has a quip about how fields are more real than particles; the idea of a "single electron" should be the idea that's abhorrent to our common sense.
