Weird problems with physics were everywhere before Einstein. Maxwell comes painfully close to discovering GR in some of his musings on black body radiation.

Noticing that there was a problem was not the breakthrough: trying something bizarre and counter-cultural - like assuming light speed is invariant over the observer - just to see if anything interesting drops out was the breakthrough.