I've recently been listening Brian Greene's The Elegant Universe and in it, he explained why Einstein started to question Newton's theory of gravitation at all. The theory explained all observational evidence - there were no experiments in that time that could not be explained by the theory. Why question it? The issue is that Newton only explained how Gravity worked. The gravitational force between two bodies is proportional to the product of their masses and inversely proportional to the square of the distance between them. Newton's theory does explain what gravity is. Newton noted this discrepancy and left that subject as a discussion topic for his readers.
The first point that Einstein realized was suspect in Newton's theory, is that the effect of gravity evidently travels instantaneously. If the Sun were to disappear, the Earth would stop orbiting it immediately, even though the light from the Sun would take 8 minutes to reach us. Einstein - fresh off of writing his paper on the Special Theory of Relativity - was wary of anything that apparently traveled faster than light speed. In his general theory of relativity, he finally answered the question of what gravity is and how it could reconcile the light speed issue. Gravity, he deduced, is the curvature of space-time in the presence of mass. That's it. In this framework, when the Sun disappears, it takes 8 minutes for us to notice, and for the Earth to stop our solar orbit.
So many of the advances in physics are deduced by taking a different perspective on an existing problem.