The American Dialect Society found 'that would be like putting lipstick on a pig' in an article published in the Washington Post on the 16th of November 1985.Before that one, they found a 1980 reference to the idea: "You can clean up a pig, put a ribbon on its tail, spray it with perfume, but it is still a pig" in the Quad-City Herald of Brewster, Washington state. (It's a good job Obama didn't use those words, or his innocence would be in serious doubt !)
I believe the original (political) user of the phrase was a woman and the subject of the phrase was not a person but a policy - as was the subject of Obama's comment.
Agree with dundrun! People assumed it was about Sarah Palin yet it was not. Mind you, John McCain just hired Sarah Palin in a cynical way to encourage female voters to vote for him and to have someone young on his team as many were put off from voting for him due to his over seniority in years. If the USA miss up on the chance to vote in Obama they will be incredibly stupid as Barrach Obama would be the best president ever for the USA plus the best USA leader as he is less gun-ho than the rest plus he would be far popular with the rest of the world methinks. Hope the USA do not blow their great chance to make Martin Luther King's speech a reality! Ciao, Beatrice35