Pluto's existence was indeed foretold by certain perturbations in the orbit of Neptune. (Not by Einstein, IIRC, however.) It and its moon Charon were eventually found about where the predicted object should have been. There's a hitch, though. The Pluto-Charon system isn't massive enough to have caused the perturbations used to predict it in the first place. Either those observations were spurious or there was something else out there.It was Lowell who predicted Pluto in 1915, but finding it fairly close to his predicted position was actually pure luck, because it isn't what causes Neptune's orbital perturbation (I think it isn't large enough); there is something else out there, as yet undiscovered.
Einstein's successful prediction was of the precession of the perihelion of Mercury's orbit, due to the distortion of space by the sun's gravitional field.