In the Wikipedia article Classical Field Theory (Gravitation), it says
After Newtonian gravitation was found to be inconsistent with special relativity, . . .
I don't see how Newtonian gravitation itself is inconsistent with special relativity. After all, Newton's Universal Law of Gravitation is completley analogous to Coulomb's Law, so it would seem that, if there were an analogous "gravitational magnetic field", one could formulate a theory of gravitation in exact analogy with Maxwell's Theory of Electromagnetism, and of course, this would automatically be consistent with Special Relativity.
What about this approach to gravitation does not work? The only problem I could see with this is the lack of evidence for a "gravitational magnetic field". That being said, gravity is "weak" as it is, and my guess is that it would be extremely difficult to set up an experiment in which a massive body were moving fast enough for this "magnetic field effect" to be obsevable.
EDIT: As has been pointed out to me in the answers, Newton itself is inconsistent with SR. Similarly, however, so is Coulomb's Law, yet, electromagnetism is still consistent with SR. Thus, how do we know that it is not the case that Newton's Law is the special "static" case of a more general gravitomagnetic theory exactly analogous to Maxwell's Theory:
Let $\mathbf{G}$ be the gravitation field, let $\rho$ be the mass density, and $\mathbf{J}$ be the mass current density, let $\gamma _0$ be defined so that $\frac{1}{4\pi \gamma _0}=G$, the Universal Gravitation Constant, let $\nu _0$ be defined so that $\frac{1}{\sqrt{\gamma _0\nu _0}}=c$, and suppose there exists a field $\mathbf{M}$, the gravitomagnetic field, so that the following equations hold:
$$
\vec{\nabla}\cdot \mathbf{G}=-\frac{\rho}{\gamma _0}
$$
$$
\vec{\nabla}\cdot \mathbf{M}=0
$$
$$
\vec{\nabla}\times \mathbf{G}=-\frac{\partial \mathbf{M}}{\partial t}
$$
$$
\vec{\nabla}\times \mathbf{M}=\nu _0\mathbf{J}+\gamma _0\nu _0\frac{\partial \mathbf{G}}{\partial t}
$$
where theses fields would produce on a mass $m$ moving with velocity $\mathbf{v}$ in our inertial frame the Lorentz force $\mathbf{F}=m\left( \mathbf{G}+\mathbf{v}\times \mathbf{M}\right)$. This theory would automatically be consistent with SR and would reduce to Newton's Law of Gravitation for the case of gravitostatics: $\frac{\partial \mathbf{G}}{\partial t}=\frac{\partial \mathbf{M}}{\partial t}=\mathbf{J}=0$. (To be clear, you can't just set the time derivatives equal to $\mathbf{0}$ as it seems I have done. Upon doing so, you obtain the corresponding static theory, which is technically incorrect (as you can easily see because it won't be relativistically invariant), but is nevertheless often a useful approximation.)
My question can thus be phrased as: without appealing directly to GR, what is wrong with this theory?
Best Answer
Newtonian gravitation is just the statement that the gravitational force between two objects obeys an inverse-square distance law, is proportional to the masses and is directed along the line that joins them. As such, it implies that the interaction between the objects is transmitted instantaneously and it must be inconsistent with special relativity (SR).
If say the Sun suddenly started moving away from the Earth at a speed very close to the speed of light, SR tells you that the Earth must still move as if the Sun were in its old position until about 8 minutes after it started moving. In contrast, Newtonian gravitation would predict an instantaneous deviation of Earth from its old orbit.
What you have discovered in your reasoning is that indeed, Coulomb's Law is NOT relativistically invariant either. But Maxwell electromagnetism is not Coulomb's Law.
As a matter of fact, Coulomb's Law is deduced from Maxwell equations as a particular case. The assumptions are those of electrostatics, namely that the magnetic field is zero and that the electric field is constant in time. These assumptions lead to the Coulomb field but they are NOT consistent with SR in the sense that they can not be valid in every reference frame since if the electric field is constant in a reference frame, then there exists another frame in which it will be varying and the magnetic field will be differnent from zero. For more you can start reading this. Maxwell's electromagnetism IS consistent with SR since the full Maxwell's equations apply in all reference frames, no matter whether the particle is moving or not.
General Relativity is the analogous for gravity of Maxwell's electromagnetism and, as it has already been said, it leads to equations for the gravitational field (the metric) analogous to those of Maxwell. Thus, it is not strange that something that resembles gravitational magnetism should appear.