How did special relativity change physicists views on the two prominent inverse square laws (ie Newton grav and Coulomb's law)? On page 107 in Hartle's Gravity -- An introduction to Einstein's General Relativity, he says the following 

With the success of special relativity it became apparent that the Newtonian theory of gravity, which had been so successfully applied to the mechanics of the solar system for almost 300 years, could no longer be exactly correct. The Newtonian gravitational interaction is instantaneous. The gravitational force $\vec{F}_{12}$ on a mass $m_1$ at a time $t$ due to a second mass $m_2$ is given in magnitude by 
  \begin{equation}
F_{12} = \frac{Gm_1m_2}{|\vec{r}_1(t) -\vec{r}_2(t)|^2}
\end{equation} 
  where $\vec{r}_1(t)$ and $\vec{r}_2(t)$ are the positions of the masses at the same instant of time. But in special relativity the notion of simultaneity is different in different inertial frames. The Newtonian law of gravity could be true only in one frame, and it would then single out that frame frome all others. The Newtonian law of gravity is thus inconsistent with the principle of relativity. 

Two Questions:


*

*Did physicists immediately realize Newtonian mechanics was incorrect after special relativity was published? Was this like a "nail in the coffin" so to speak or was Newtonian gravity already suspect to begin with? I remember reading that perihelion precession of Mercury was known well before SR was theorized. So is Hartle's account the way it developed historically or is this an example of after-the-fact distortion of what happened because that's how we think of it now? 

*Did physicists draw the same conclusion about Coulomb's law? If so, what did they replace it with? Maxwell's equations and the Lorentz force law? Is this part of why Maxwell's equations are so coveted?

 A: 
Did physicists immediately realize Newtonian mechanics was incorrect after special relativity was published?

Of course not. Physicists did not immediately realize that Einstein's description of electromagnetism (the second part of his 1905 paper on special relativity) was correct after special relativity was published. I can't think of a single scientific theory that represented a radical change that made scientists immediately realize that their old ways of thinking were incorrect. Quoting Max Planck, "Science advances one funeral at a time."

Was this like a "nail in the coffin" so to speak or was Newtonian gravity already suspect to begin with?

Newton himself was the first to suspect his action at a distance formulation for gravity:
That gravity should be innate, inherent, and essential to matter, so that one body may act upon another at a distance through a vacuum, without the mediation of anything else, by and through which their action and force may be conveyed from one to another, is to me so great an absurdity that I believe no man who has in philosophical matters a competent faculty of thinking can ever fall into it. Gravity must be caused by an agent acting constantly according to certain laws; but whether this agent be material or immaterial, I have left open to the consideration of my readers. (Newton in a letter to Richard Bentley)
Laplace worked on adding a transmission delay to Newton's gravitation formula. It didn't work. He found that unless the transmission speed was exceedingly fast, many millions of times that of the speed of light, such a delay to Newtonian gravity would make the solar system unstable. Science was stuck with action at a distance gravitation for another 100 years.

Did physicists draw the same conclusion about Coulomb's law? If so, what did they replace it with? Maxwell's equations and the Lorentz force law? Is this part of why Maxwell's equations are so coveted?

Maxwell's equations include Gauss' law, which can be used to derive Coulomb's law as a special case where two charged particles are held in place. The Lorentz law postdates Maxwell's equations by about 30 years.
Resolving the apparent discrepancy between Maxwell's equations and Newtonian mechanics, compounded by the Michelson-Morley experiment, was one of the big problems in physics in the late 19th century. Poincaré and Lorentz took an approach that tried to rescue Newtonian mechanics. Einstein took a different approach. We remember that different approach. Getting back to the answer to the first question, a number of physicists of Einstein's time did not appreciate that different approach.
