The discovery of Neptune is one of those neat stories often used to illustrate the predictive capabilities of science. Englishman John Couch Adams and Frenchman Urbain Jean-Joseph Le Verrier independently calculated the orbit of the inferred new planet, based on known irregularities in the orbit of Uranus. And, sure enough, when astronomers pointed their telescopes where Adams and Le Verrier said, there shone Neptune! Interestingly, though, these astronomers were probably not the first to observe Neptune: Galileo, Lalande and Herschel are each thought to have seen the it earlier, but none of them seems to have realised that they were looking at a new planet.
Another frequently told story of a scientific prediction proving correct comes courtesy of Charles Darwin. (You must have known I'd be getting to him eventually.) In his snappily titled book On the Various Contrivances by which British And Foreign Orchids are Fertilised by Insects, and on the Good Effects of Intercrossing, Darwin famously predicted the existence of a moth with an extremely long proboscis, which would be the pollinator of a strange Madagascan orchid with an extremely long nectary, writing:
I fear that the reader will be wearied, but I must say a few words on the Angræcum sesquipedale, of which the large six-rayed flowers, like stars formed of snow-white wax, have excited the admiration of travellers in Madagascar. A whip-like green nectary of astonishing length hangs down beneath the labellum. […]
I could not for some time understand how the pollinia of this Orchid were removed, or how it could be fertilised. I passed bristles and needles down the open entrance into the nectary and through the cleft in the rostellum with no result. It then occurred to me that, from the length of the nectary, the flower must be visited by large moths, with a proboscis thick at the base; and that to drain the last drop of nectar even the largest moth would have to force its proboscis as far down as possible.
Darwin's prediction was seen as a bold one by at least one of his correspondents. In 1862, just 16 years after the discovery of Neptune, Edward Cresy Jr went so far as to compare Darwin's prediction with that of Adams and Le Verrier, writing to Darwin:
I think your anticipation by analogy of a Madagascar moth with a probiscis ten inches long equals Adam's & Leverrier— What a triumph it will be to find him—
Unlike Adams and Le Verrier, Darwin did not live to see his prediction confirmed. It was not until 1903 that a new sub-species of the African hawk moth was discovered in Madagascar. As Darwin had predicted, the moth feeds from the nectaries of Angraecum sesquipedale with its extremely long proboscis. The new sub-species was given the very appropriate scientific name Xanthopan morganii praedicta in recognition of yet another triumphant prediction for science.
Postscript [02-Dec-2011]: …although, apparently (see comments), Xanthopan morganii praedicta was named in honour of Alfred Russel Wallace's similar prediction, not Darwin's.