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.