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.
Imagine a closed curve in space. Lets say there is an electric field circulating around this curve, just going around, not going into or outside. The imaginary curve then Maxwell tells us that the circulation of the electric field around the curve will cause a 'flow' of the magnetic field on the perpendicular direction to the curve (the magnetic field is always perpendicular to the electric field. In a similar manner, if you now imagine the magnetic field circulating around a closed curve, Maxwell tells us that a similar thing will happen, in this case there will be an electric field flowing on the direction perpendicular to the circulation of the magnetic field. This also explains why light needs no medium to propagate, as opposed to a classical wave. If at some point in space you have a charge moving, lets say it creates a magnetic field, this in turn will create a flow of the magnetic field in the perpendicular direction of motion and so on through space until it reaches your eyes.
Best Answer
Inconsistency between two theories just means that there are statements that one theory says are true, and the other says are false.
An easier example than the one you're asking about is the inconsistency between Newtonian mechanics and special relativity. Newtonian mechanics says that if you keep applying a force to a material object, it will eventually go faster than the speed of light, c. Special relativity says that this statement is false.
Your example of Newtonian mechanics versus Maxwell's equations is a lot more subtle. If you'd asked someone in 1890, they probably would have said that Maxwell's equations were consistent with Newtonian mechanics, but they simply described different aspects of nature. In order to maintain this consistency, they were forced to say that Maxwell's equations had their simplest form in one preferred frame of reference, which was believed to be the frame of the ether. What they didn't realize was that the transformation of distance and time measurements from one frame of reference to another was not described correctly by the equations they'd been assuming. Using the correct, relativistic transformations, Maxwell's equations have the same form in all frames. Today, physicists think of Maxwell's equations as being inherently based on special relativity; but that wasn't how people in 1890 thought of them.