Actually Galileo first observed Neptune in 1612, but he thought it was a star because he happened to see it exactly when it was turning retrograde (changing its apparent direction when seen from Earth). How's that for bad luck?
It was finally discovered after a couple of smart people did some impressive number crunching of Uranus's orbit and found that it was doing something wonky. They guessed that another planet was perturbing its orbit, and told people exactly where to look, but couldn't get any astronomers interested. It took three more years before Neptune was spotted, just about where it was predicted to be. The British and French then fought over who had the rightful claim to the discovered.
This is akin to how they find exoplanets -- planets circling other stars -- today, although they look for wobbles in a star's position, not another planet's. The perturbation predictions don't always pan out -- a planet named "Vulcan" was proposed to exist between the Sun and Mercury in order to account for the unexplained piece of Mercury's orbit, whose ellipse "precesses," or rotates, by 574 arcseconds per century. Astronomers could account for all but 43 of those arcseconds, but never did find Vulcan. Instead Einstein found the missing amount exactly from his theory of general relativity, showing it was due to the slight curvature of spacetime through which Mercury travels. Einstein experienced heart palpitations when he finished his arithmetic and got 43 arcseconds/century, and was "for several days beside myself with joyous excitement."