You're getting at one of the ways that the world most mystifies people- the apparent existence of forces at a distance. It turns out that there really is something carrying the force between the magnets- a magnetic field. The field isn't visible and can't be felt by non-magnetic objects, so it seems like there's nothing there, but it really is there. It can be measured with all sorts of instruments, including a little compass.
So the question becomes whether saying there's a magnetic field is just renaming the fact of action at a distance or whether the field really should be seen as an ingredient of the physical world. The main symptom of the field being real is that it takes a while to propagate from one place to another.
Say you turn on an electromagnet. How soon will it start pulling on a distant magnet? If it started immediately, you might say there was action at a distance, and the field was a mere name. It doesn't. The other magnet doesn't feel anything until a little time has elapsed. The field propagates at the speed of light. Admittedly the delay times are short for distances on earth, but they're easily measurable with common lab instruments.
p.s. I've marked your question as stand-alone, rather than leaving it at the tail end of a long thread.
(published on 12/10/2011)