The fundamental issue is his notion that new theories, such as the heliocentric model of the solar system, are incommensurable (or incompatible) with old theories, such as the geocentric model of the solar system. But what about cases such as physics or evolutionary biology?
Did Einstein's ideas replace Newton's, or augment them? Well, kind of both. In the theoretical framework of Newton, matter is immutable. In the Einsteinian framework, matter may be transformed into energy. In a Newtonian framework, there is the concept of absolute time...the universe has a central clock, if you will. In the Einsteinian framework, there is no concept of absolute time or absolute simultaneity...whether or not two events occur at the same instant depends on the frame of reference from where the observation is made. So yes, in one sense the Einsteinian theoretical framework is not compatible with Newton's.
On the other hand, we obviously didn't toss Newton's work in the trash can. Many of the fundamental precepts he laid out are still valid in a particular frame of reference. In this sense, Einstein's ideas didn't replace Newton's, but augmented them.
So in a way I think the issue may just be a semantic one, and really not all that interesting. Kuhn was not a relativist, thinking we just bounce around between explanations. In the postscript to the 2nd edition of SSR, he writes:
Later scientific theories are better than earlier ones for solving puzzles in the often quite different environments to which they are applied. That is not a relativist's position, and it displays the sense in which I am a convinced believer in scientific progress.
I also think Kuhn would acknowledge that the achievement of a new paradigm is dependent upon all the work that has come before. Einstein was an anti-establishmentarian, and developed many of his ideas by rejecting some of the most entrenched assumptions in physics at the time. But his theories would have been impossible to develop without all of the work that had come before him.
Maybe Kuhn would disagree with this, and I'm misunderstanding him. If he is, then he's saying something much more radical than what I realized. But I don't think so.