What was wrong with action a distance? It is usually said that the idea of fields was introduced (electric and magnetic fields) in electricity and magnetism after Coulomb's law to cure the conceptual problems of action at a distance.
Could someone explain what are the conceptual and physical difficulties or contradictions that one might have with action at a distance?
 A: In Newtonian physics, there was no problem with action at a distance, and indeed Newton explicitly formulated his theory of gravitation in such terms. It may be that this was criticised from a philosophical standpoint (I don't know whether it was or not), but there were no fundamental mathematical difficulties with the idea.
However, in relativity the picture changes quite dramatically. The problem is this: action at a distance means that one object is able to influence another instantaneously, but in relativity this idea doesn't really make sense, as I will now explain.
In the Newtonian picture of gravity, if we have two massive objects separated by some distance, and one of them starts moving (perhaps because some distant object has exerted a force on it via a long cable) then the forces on the other one will change at exactly the same moment in time. But in relativity, what happens at "exactly the same time" is different depending on the velocity of the observer. If you and I are travelling at different speeds, and I observe the two objects' motion to change simultaneously, you might see the second object moving before the first one, which would be very strange indeed.
Because of this, you can't have action at a distance in relativistic space-time. (Well, I guess you can if there's a special preferred reference frame, but this causes conceptual difficulties relating to causality as hinted at above, and it can easily be refuted experimentally.) From this you can conclude that all influences must be local. In general relativity, gravitational influences propagate no faster than the speed of light.
But having said all that, Maxwells equations were developed before relativity rather than the other way around, so historically it isn't true that the idea of a field was developed to resolve this particular difficulty. 
A: Contrary to a common misconception in physics, there is nothing wrong with action-at-a-distance.
In fact, it is field theory which has well-known difficulties: divergences, violation of causality, inability to deal with general two-body motion...
As shown by Feynman and others, the well-known difficulties of the field theory of electromagnetism are solved by action-at-a-distance:
Classical Electrodynamics in Terms of Direct Interparticle Action
Cosmology and action-at-a-distance electrodynamics
A: Nothing was wrong. It was just inconvenient and now the preference is to the local theories. 
You are not quite correct saying that the fields were introduced to save the locality. 
At school I was taught that if you consider the system of the particles which interact electromagnetically then the energy of the particles is not conserved. People do not like to drop the idea of energy and momentum conservation, so it was decided to count the field energy and the energy and momentum conservation were saved. The resulting picture was local. Now people often start from the postulate of locality, but it is not a fundamental rule or something. In some sense, the local theories are simpler and more convenient and it is tricky to fit non-local theories into relativistic physics as Nathaniel mentioned. That's all. 
A: Quite easily. Imagine 2 bodies of equal mass moving at a constant speed on opposite sides of the same circle centered on a fixed point under the influence of a mutual attraction. They are experiencing equal and opposite forces, while the total momentum (and mass moment) of the 2-body system is 0.
Under a Lorentz transform, say, along the y-axis, where the circle is in the xy-plane, to a frame in which the 2-body system is moving steadily upward along the y-axis, there is a transform of synchronization in the y-direction as well, such that the body higher on the y-axis has a later clock reading than the one below it. So, it crosses the y-axis first, as it rounds the corner.
That means the two bodies are not experiencing equal and opposite accelerations. And it means the total of the forces they are subject to are not equal and opposite; nor is the total mass moment, relative to the position of the moving center. There's a deficit brought about by the desynchronization of the two bodies; a little bit of the "equal and opposite" action-at-a-distance force of the upper body on the lower one hasn't yet reached the lower body but is lingering somewhere between the two.
Recall: the action at a distance in Newton's Third Law says "equal and opposite forces AT THE SAME TIME" (i.e. propagating at infinite speed) "between the two bodies [in a direction parallel to the line separating the bodies]" The Lorentz transform of instantaneous action or infinite speed is finite speed faster than light. So, for Newton's Third Law to be consistently translated to relativistic form, you would need to somehow account for this in-between condition of the extra impulse that has not yet gotten to the other body.
The usual No-Interaction theorems (Leutwyler, Haag) assume that many-body dynamics have additive momentum - that is: that the momentum of the system is equal to the sum of the momenta of its parts. As a result -- almost directly, as you see by the description above -- it concludes that the interaction between the bodies must be 0. The way the Leutwyler Theorem is proven is to start out by assuming that angular momentum and momentum are additive, that energy is additive, up to the inclusion of many-body potential, and that the total mass momentum transforms consistently under Lorentz transforms. It stumbles into the above-mentioned problem with the mass moment deficit (because it had already started out by by assuming the momentum deficit was 0) and draws from this the conclusion that the potential energy must also be 0.
In non-relativistic theory, it is actually possible to codify the instantaneous transmission of impulse as a symplectic representation of the Galilei group (or equivalently: a mass 0 representation of the Bargmann group); whose principal features are (a) that they have an invariant momentum-squared, which might be regarded as the value of the impulse associated with the representation, (b) are instantaneous (no time translation invariance) and (c) no mass. So, a continuously-acting force might be regarded as a time-densitized continuum of such representations.
Perhaps a similar thing might be possible in relativity. The relativistic versions of the symplectic representations just described above are both the luxon (light speed) and tachyon (faster than light speed). The former might be regarded as a carrier of the radiation, the 1/r part of a force. In contrast, the latter might be regarded as a carrier of instantaneous 1/r^2 part of a force. In electromagnetism it is marginally possible to completely account for electromagnetic forces as a transmission of luxons. But ultimately it led to the Wheeler-Feynman absorber theory, whose problems were never fully resolved.
The idea of using the latter possibility was probably considered first by Wigner when he laid out the "Wigner classification" in 1939 (out of which we get the classes: bradyon/luxon/tachyon/homogeneous). He said in the 1939 paper that he eventually wanted to get back to the tachyons, but apparently never got around to it ... until much later.
A lot of people tried to devise different formulations for a consistent relativistic many-body dynamics in the 1950's-1970's; and probably the best push in that direction was the general framework that Van Dam and Wigner laid out for possible action-at-a-distance forces mediated by faster-than-light non-instantaneous lines of force. ("Classical Interacting Relativistic Mechanics of Interacting Point Particles", Physical Review, 138, B1576-1582, 1965; "Instantaneous and Asymptotic Conservation Laws for Classical Relativistic Mechanics of Interacting Point Particles", Physical Review, 142, 838-843, 1966.)
Apparently, that was Wigner's "finally getting back to the tachyon" issue, though he didn't specifically state it as such. Nonetheless, his and Van Dam's description amounts to doing the very kind of time-densitized smearing out of representations that I described above. (The integrals used to describe the interaction, in fact, express a time-smeared continuum of luxons and/or tachyons between the interacting bodies; they consider both sets of possibilities.)
In the view espoused in Van Dam and Wigner's treatments, these representations are not "particles" but merely the relativistic version of Newton's instantaneous lines of force caught in an in-between state. They account for the momentum deficit in a way that is compatible with the Lorentz transformation.
There's one more recent approach that I've seen that carries promise in that direction, though the author does not explicitly sell it as a "force mediated by FTL action-at-a-distance" idea. (Actually he sorta does: below equation (23) in his paper where it says q is a "spacelike momentum" -- well, that's just another name for a tachyon. He acknowledged that point, but still insisted on shying away from it.)
Reverse Engineering Approach to Quantum Electrodynamics
Smilga
arXiv: 1004.0820v2 physics.gen-ph
In his approach, when one lays out the 2-body scattering scenario used in the perturbative S-matrix formulation of quantum field theory, the initial "in" state consists of 2 bodies, as does the final "out" state; but the intermediate states are also given interpretation as consisting of a 2-body system, that has a well-defined total momentum (P = p0 + p1) but is an entangled state with an intermediary (q) that effectively communicates that entanglement.
The out state that emerges can be thought of as doing a momentum measurement on one of the two bodies (p0') which clamps down on (q), and which by virtue of the relation (p1' = P - p0') also clamps down on the momentum of the other body. Whatever the difference is I = p0' - p0, is an impulse in effect that is equal and opposite to the impulse -I = p1' - p1 of the other body. So, a separated in state becomes an entangled interacting state, and separates again as an out state after the impulse is transmitted via the entanglement.
He actually goes on, and develops that idea further (in other articles) that action at a distance can, itself, be constructed in a similar way via entanglement; though I think he goes too far in trying to do such things as derive the fine structure constant from all this!
A: There was, and is, nothing wrong with "action at a distance". We still use action at a distance. The difference is that today, we specify the speed of transmission of action.
"We turn on the switch and the bulb lights" - is an action at a distance. The action is transmitted at speed of electricity. Even "turning on the switch" itself is an action at a distance, the distance involved is at sub atomic level. We never actually touch the switch. Gravity still is action at a distance with transmission speed of c. Actually "action at a distance" is only thing that makes sense, just the distances vary, and the speed of transmission vary.
Then relativity comes into picture where "reaching of signal" is treated as time of event occurrence. In fact that is time of observation of the event, not occurrence of it. Due to this, different observers can disagree on timing of events depending upon relative speeds of events and observers involved.
