Mind the Gap
The answer is yes.
We looked at the two major-party (or most major) candidates in every contested election. You will recall that the 1789, 1792, and 1820 elections were effectively unopposed -- and there is the wild 1836 election where the Whigs ran regional candidates against Martin Van Buren -- we went with William Henry Harrison as the comparison here.
The biggest previous differential is the 1996 Dole-Clinton race -- Senator Dole is 23 years senior to Bill Clinton. Two other races had nearly as large gaps, the 1992 election between Clinton and George H. W. Bush had a 22 year difference, and the 1856 election between James Buchanan and John C. Fremont (at left) also had a 22 year spread.
Barack Obama will be 47 on election day 2008, and John McCain will be 72. Their 25 year gap would set a record.
As a side note, there appears to be no pattern to whether the younger or older candidate wins.
