‘There’s nothing new under the sun” is a phrase from the Book of Ecclesiastes.
 
“The oldest word in politics is ‘new’” is cited in print from at least 1998, when it was used in the race for governor of California. The phrase may be related to the formation of the “New Labour” party in the United Kingdom in 1994.
 
In October 2008, the phrase was used to describe Barack Obama’s “new” politics—which some critics thought reflected “old” Democrat principles from at least the 1930s.  Charles Kesler wrote an online Wall Street Journal opinion, published October 21, 2008: “As they say, the oldest word in American politics is “new.”  About a week later, Jonah Goldberg wrote: “There’s an old saying: The oldest word in American politics is ‘new.’”
 
     
Wikipedia: Labour Party (UK)
New Labour
Tony Blair moved the party further to the right, adopting policies which broke with Labour’s socialist heritage at the 1995 mini-conference in a strategy to increase the party’s appeal to “middle England”. 
 
“New Labour” was first termed as an alternative branding for the Labour Party, dating from a conference slogan first used by the Labour Party in 1994 which was later seen in a draft manifesto published by the party in 1996, called New Labour, New Life For Britain. The rise of the name coincided with a rightwards shift of the British political spectrum; for Labour, this was a continuation of the trend that had begun under the leadership of Neil Kinnock. “New Labour” as a name has no official status but remains in common use to distinguish modernisers from those holding to more traditional positions who normally are referred to as “Old Labour”. New Labour has been used a derogative term by some to separate the “Thatcherite” policies adopted by Tony Blair and Gordon Brown to that of Old Labour and the old Clause 4.
 
25 October 1998, Sacramento (CA) Bee, “In California Governor’s Race, Gray Davis, Dan Lungren Are a “Fire and Ice’ Contrast in Policies, Temperaments,” pg. EL1:
The oldest word in American politics is “new,’ and it’s just hard for Gray Davis to paint himself as a new-ideas politician. He just isn’t.”
   
Simon World
And let’s not forget, as people pointed out at the time of ‘New’ Labour in the UK, that ‘New’ is the oldest word in politics!
posted by: Richard W on 06.22.05 at 10:15 PM
     
The Wall Street Journal
OPINION: FEDERATION FEATURE
OCTOBER 21, 2008
The Audacity of Barack Obama
He thinks liberals can get beyond the old debate by finally winning it.
By CHARLES R. KESLER
(...)
The clash between hope and cynicism pits the future against the past, “a new politics for a new time” against the same old, same old. Despite Mr. Obama’s occasional impatience with progressivism’s rosy view of human nature, his reliance on the formula of the past versus the future—and on the “living Constitution” to weave them together—confirms his deep debt to Wilsonian-style Progressivism, which has dominated the Democratic Party’s consciousness for a hundred years. As they say, the oldest word in American politics is “new.” 
 
Bowling Green (MI) Daily News
Obama’s not new
Candidate’s politics are the same as FDR’s, just a different face
By JONAH GOLDBERG
Thursday, October 30, 2008 11:27 AM CDT
There’s an old saying: The oldest word in American politics is “new.” Only in that sense is there anything new to Barack Obama.
 
Obama prefers the word “progressive” to “liberal” because it makes it sound like he’s shedding old liberal ideas. But if he is, it’s only to embrace older ones.