Fundamental paradox with Newton's Law of Gravity? This is my first post here, but I've been struggling with this problem in my head since I studied physics at school when I was 14 (30 years ago!).
There seems to be a fundamental paradox with Newton's Law of Gravity (NLG), but it can't have anything to do with general relativity, because the masses and speeds involved can be negligible and you still get the paradox...
Imagine two bodies, A and B with mass $M_a$ and $M_b$, respectively, separated by a distance of $r$.  Now according to NLG:
If you're standing on A, then B accelerates towards you at $$(G M_a M_b / r^2) / M_b = G M_a / r^2.$$
And if you're standing on B, then A accelerates towards you at 
$$(G M_a * M_b / r^2) / M_a = G M_b / r^2.$$
But $M_a \ne M_b$.
So how can two different observers on A and B see accelaration towards each other at very different rates, even if the masses and speeds involved are negligible (barely affected by relativity)?
And why didn't Newton himself see this paradox?
Finally, how can/should NLG be modified to resolve this paradox, and still fit observations at low masses and speeds?
 A: Your misconception has nothing to do with gravity - you're just getting a little mixed up about acceleration vs. relative acceleration.
Let's dispense with gravity, since it's a red herring here. Say there are two cars. Car A accelerates at $+3 ~\rm m/s/s$ (to the right). Car B accelerates at $-5 ~\rm m/s/s$ (that is, to the left). So far, so good, right? There's no paradox about two cars accelerating at different rates.
Now, suppose you are sitting in car B. If you want to measure the apparent, or relative, acceleration of car A relative to you, you just take the difference of the accelerations:  $(3) - (-5) = 8 ~\rm m/s/s$. So car A is accelerating at $8 ~\rm m/s/s$ relative to car B.
If you're the driver of car A, and you want to measure the apparent acceleration of car B relative to you, you follow the same procedure:  $(-5) - (3) = -8 ~\rm m/s/s$. So car B is accelerating at $-8 ~\rm m/s/s$ relative to car A.
That seems perfectly intuitive and contradiction-free to me. The magnitude of the relative acceleration of each car is equal, as it must be, since the relative acceleration of each car relative to the other represents the rate at which the separation distance is decreasing, which must be equal for both of them.
Going back to your example, the magnitude of the relative acceleration of the masses is $G M_a / r^2 + G M_b / r^2$†. Even though they have different accelerations in the frame of reference you chose at the beginning of the problem, their relative acceleration is the same.
† if you're wondering about the plus sign, consider that gravity produces accelerations in the two bodies that are opposite in direction, which we must represent by giving one of the two accelerations a negative sign. When we take the difference between the accelerations, that negative sign becomes a plus.

If you'd like a justification of the "take the difference of the acceleration" procedure, since it's the heart of my argument, here it is:
Let $x_a$ and $x_b$ be the positions of the two cars. The separation of the cars must be 
$$s = x_a - x_b$$
If we want to know the rate of change of the separation of the cars, we can take the derivative of that equation: 
$$\frac{ds}{dt} = \frac{dx_a}{dt} - \frac{dx_b}{dt}$$
If we take the derivative again, it should give us the rate of change of the rate of change of the separation, which is the relative acceleration:
$$\frac{d^2s}{dt^2} = \frac{d^2x_a}{dt^2} - \frac{d^2x_b}{dt^2}$$
The two quantities on the right side are simply the accelerations of two objects, $a_a$ and $a_b$, so 
$$\frac{d^2s}{dt^2} = a_a - a_b$$
A: It doesn't have to be modified, it's fine as it is. There's no paradox at all.
The force that attracts both to each other is indeed $F=G\frac{M_A M_B}{r^2}$.
But the acceleration they experience is not the same (at least provided $M_A \neq M_B$) because their inertias (masses) are not the same. For one $F=M_A a_A$, for the other $F=M_B a_B$.
There's no paradox or contradiction and nothing to 'fix'..

In that diagram, $F=G\frac{M_A M_B}{r^2}$.
Earth accelerates at $a_A=G\frac{M_B}{r^2}$, Jupiter at $a_B=-G\frac{M_A}{r^2}$.
The minus sign accounts for the sense of the $x$ axis and that the accelerations are in opposite directions.
A: The acceleration they experience locally is different due to the different masses, whilst the acceleration they experience one to the other is of course equal (or at least synchronizing during any approach), otherwise A would hit B (when the planets crash together) later or sooner than B would hit A.
