Einstein was definitely ahead of the curve, but wasn't running on zero data, even if we discount the purely mathematical issues, such as the inability to reconcile the lack of a reference frame in the Maxwell equations with the need for a reference frame for all other physics of the time.
(It might be worth pointing out here that relativity itself was not a new concept; now when we say "relativity" we mean Einsteinian relativity, but there is also, for instance, "Galilean relativity". Relativity wasn't a surprise, it's just nobody could make it all work out properly without contradictions until Einstein.)
I really recommend this online book: http://www.mathpages.com/rr/rrtoc.htm It is both a great (IMHO) introduction to relativity, Einsteinian and otherwise, and also has a lot about history of Einstein's theory and the general state of thought at the time. I do not mean to diminish Einstein's accomplishment, because like I said he legitimately was ahead of the curve, but it wasn't quite the "bolt from the blue" that it is often portrayed as. All the math pieces Einstein needed had been developed, and his genius was largely the combination of figuring out how to put them together in a way that explained reality, and doing so while discarding inappropriate assumptions that were holding back the physics community at large. I'm actually more impressed by the latter, lest you think I'm trying to diminish that accomplishment; that's a hard harder than that sentence may make it sound.
Have you seen those string theorists? I'm not a big fan of string theory, but anyone who can even remotely navigate those things could work out GR in a few afternoons, with all the advantages another 100 years of evidence and developments would bring. (Sort of a weird thing to say since it's already worked out, but still.)
You think all those smart people would just be diddling around, going, gosh, I sure wish I could reconcile this overwhelming data that points at a 100+ year-old mathematical formalism, but I guess we'll just have to dick around for a while longer!?
It didn't take very long before it was decided that the switch needed to be permanently in the 'on' position, and it was dropped from subsequent models.
EDIT: makes you wonder if Einstein had not made his predictions regarding relativity, this would have been the first real opportunity to find out in a 'natural' way, how long it would have taken them based on the observation that things did not work as intended.