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.
Poincaré was confused on several points. (See the discussion on Wikipedia regarding "mass energy equivalence".) He could never get the mechanical relations straight, since he could not figure out that $E=mc^2$. Einstein followed Poincaré closely in 1905, he was aware of Poincaré's work, but he derived the theory simply as a geometric symmetry, and made a complete system.
Einstein did share the credit with Lorentz and Poincaré for special relativity for a while, probably one reason his Nobel prize did not mention relativity. Pauli in the Encyclopædia Britannica article famously credits Einstein alone for formulating the relativity principle, as did Lorentz. Poincaré was less accomodating. He would say "Einstein just assumed that which we were all trying to prove" (namely the principle of relativity). (I could not find a reference for this, and I might be misquoting. It is important, because it shows whether Poincaré was still trying to get relativity from Maxwell's equations, rather than making a new postulate—I don't know.)
Special relativity was ripe for discovery in 1905, and Einstein wasn't the only one who could have done it, although he did do it best, and only he got the $E=mc^2$ without which nothing makes sense. Poincaré and Lorentz deserve at least 50% of the credit (as Einstein himself accepted), and Poincaré has most of the modern theory, so Einstein's sole completely original contribution is $E=mc^2$.
Best Answer
There was no problem with electromagnetism. The problem was that Maxwell's equations are invariant under Lorentz transformations but are not invariant under Galileo transformations whereas the equations of classical mechanics can be easily made invariant under Galileo transformations.
The question was: how to reconcile both in a universe in which Maxwell's equations had been tested much more thoroughly than the equations of classical mechanics when $v$ is in the same order of $c$ and not much smaller.
Einstein basically solved the problem by deciding that electromagnetism is more fundamental in physics, and then showing that classical mechanics could be modified in such a way, that it, too, became Lorentz invariant. As a side effect, he recovered classical mechanics as a natural limit for $v/c\to0$, which perfectly explained almost all observations of macroscopic dynamics available at that time (leaving Mercury's perihelion precession to be explained by general relativity ten years later).