How universal gravitation falls short As a non physicist I can understand how Newtonian mechanics falls short in cases of high velocity etc. and is properly generalized by the special theory of relativity.
What is not clear to me is how universal gravitation falls short: under what conditions does it fail to make accurate predictions?  What are the cases where the inverse square law actually fails to give accurate results and the general relativity is needed?  I do understand that Einstein's theory provides the mechanism, whereas Newton's did not.
Assuming a hypothetical system involving a black hole and a planet like the earth revolving around it (far beyond the horizon, of course) would universal gravitation fail to accurately predict the behavior of the system?
 A: Generally speaking, and provided you don't stray too close to black holes, you can imagine GR as making small modifications to Newton's law. For example Newton tells that the acceleration of a body falling towards a planet of mass M is:
$$ a = \frac{GM}{r^2} $$
i.e. the famous inverse square law. If you calculate the acceleration for a Schwarzschild metric (which describes spherically symmetric bodies) you get:
$$ a = \frac{GM}{r^2}\frac{1}{\sqrt{1-\frac{2GM}{c^2r}}} $$
(This was calculated in this answer; do feel free to upvote as I think this is a nice calculation, though there are some subtleties to it that you need to read that answer to understand.)
So GR modifies the inverse square law by the factor:
$$ \frac{1}{\sqrt{1-\frac{2GM}{c^2r}}} $$
The modification is small as large distances i.e. when the distance $r$ is much greater than $c^2/2GM$. To give some idea of scale, at the Earth's distance from the Sun the factor is about 1.00000001 so it's almost negligable. Even right at the Sun's surface the factor is still only 1.000002. You need to get close to a black hole for the factor to increase much, and indeed right at the event horizon it goes to infinity!
These corrections to Newton's law may seem small, but they are responsible for phenomena like the precession of Mercury. Although the precession is a well known test of GR, people tend to forget just how small is is. It would take over 4,000 years for the precession to rotate Mercury's orbit by the angle subtended by the Moon from Earth (half a degree).
A: Some of the conditions for Newtonian gravitation to work are:


*

*All particles must be slow, as compared to the speed of light in vacuum. The Newtonian potential $\Phi$ must must likewise not change too fast. This is simply because Newtonian theory is incompatible with a characteristic speed $c$.

*The Newtonian potential $\Phi$ must be small, $|\Phi/c^2|\ll1$. If it is not small, then spacetime is strongly curved and predictions of GTR start to vary sharply with Newtonian theory. (Or rather, with strong curvature, there is no meaningful $\Phi$ in the first place.)


It really doesn't matter whether this is a $2$-body system or a more complicated one. If you already know that spacetime geometry should be described by a metric, then under the above assumptions you can work backward from Newtonian theory to see what kind of spacetime would approximate it: the action for Newtonian gravity is
$$\text{Newton} = \int \left(\frac{1}{2}v^2 - \Phi\right)dt$$
so with low velocity $v = dS/dt$ and gravitational potential $\Phi$, we can approximate it with
$$\int dt\sqrt{\left(1+2\frac{\Phi}{c^2}+4\frac{\Phi^2}{c^4}\right) - \frac{1}{c^2}\frac{dS^2}{dt^2}}= \int\left(1+\frac{\Phi}{c^2}-\frac{1}{2}\frac{v^2}{c^2} + \mathscr{O}\left(\frac{v^4}{c^4},\frac{\Phi^3}{c^6},\frac{v^2\Phi}{c^4}\right)\right)dt\text{,}$$
which works because of the MacLaurin series $\sqrt{1+x} = 1+\frac{1}{2}x -\frac{1}{8}x^2 + \ldots$. Note that scaling by or adding a constant not change any physics, since the same trajectories extremize the action. Therefore, for low speeds and small, slowly-varying Newtonian potential, the predictions of Newtonian theory are very close to those of a spacetime metric
$$ds^2 = -\left(1+2\frac{\Phi}{c^2}+4\frac{\Phi^2}{c^4}\right)c^2dt^2 + \underbrace{dx^2+dy^2+dz^2}_{dS^2}\text{.}$$
But even under those conditions, this is still a bit wrong from experiment, because even under the assumption of a slowly-changing weak gravitational field, this is not the correct post-Newtonian expansion of GTR. It gets the deflection of light wrong by a factor of $2$, which is correct for Newtonian theory in the sense of deflection of a particle with $v\approx c$, and predicts no perihelion shift for Mercury (even for an idealized Sun-Mercury $2$-body system).
Edit: Added one more term in the metric to make it 'more Newtonian', in the sense of getting rid of perihelion shift (which Newtonian theory proper shouldn't have) and matching the action to higher order than before.
A: This is a very broad question with a huge list of answers.  I don't think it's realistic for a complete treaties of the subject.
The failure of Newton's Universal Gravitation isn't in the "inverse square law".
With universal gravitation:


*

*There is no maximum speed

*Time doesn't slow down in a gravitational field

*Light would not bend in a gravitational field (or red / blue shift)


Before general relativity one of the biggest outstanding issues with universal gravitation was the anomalous precession of Mercury's orbit.  To an external observer, your hypothetical "Earth orbiting a black hole" (ignoring tidal forces that would tear the Earth apart) would display extreme deviations from the predictions of universal gravitation because time would be passing slower for the system.  It would be much more significant than Mercury's perihelion shift.
Gravitational waves and the loss of energy in a two-body system is another prediction of general relativity which has been confirmed a few times.  For example with PSR B1913+16.
In general, I'd suggest looking at various tests of general relativity because in most cases testing general relativity is predicated on the breakdown of universal gravitation.
A: In broad terms, Newtonian gravity fails when gravitational accelerations become potent enough to result in relativistic speeds. In other words, Newtonian gravity is a weak gravity theory that breaks down when the gravitational potential $GM/R$ becomes comparable to $c^2$, the speed of light squared. 
Newtonian gravity provides us with an excellent approximation that works extremely well in our daily lives. This can be seen from the fact that the gravitational potential at earth's surface is nothing else than the square of Earth's escape velocity ( $v_{escape} = 9.8 m/s$ ), which is much smaller than the square of the speed of light ( $c = 300,000,000 m/s$ ).
See the above as a rule of thumb. There is much more to be said about this subject. Google for "Post-Newtonian approximations" to learn more.
A: The earlier answers were correct and well stated. I like looking at things from an intuitive angle.
Newton showed, via calculus, that the path of an object under an inverse-square law force is an ellipse, with the object going faster as it gets closer to source of the force (at one focus of the ellipse). 
Universal gravity is an inverse-square law AS LONG AS THE NUMERATOR IS CONSTANT. In Mercury's case, the numerator is G x mass of sun x mass of mercury.
But relativity says that the mass of an object increases with its velocity. So, as Mercury gets nearer the sun, and its velocity increases, its mass increases. The force of gravity between the sun and Mercury is now a little higher than it "should" be. The numerator in the universal gravity formula is not staying constant. So Mercury does not travel a perfect ellipse.
Perhaps this helps you picture how relativity can alter the behaviour predicted by standard Newtonian mechanics.
-Rob 
