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 completely 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 observable.
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 these 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?