You have probably seen some incarnation of this snowclone in the last week, if not more recently. (“Knitting is the new yoga“?)
Ben Zimmer has already traced the origin of this one: it was attributed to Gloria Vanderbilt as “pink is the navy blue of India,” but Diana Vreeland actually said it in the early 1960s. Thus we might describe the etymology as an instance of the “X is the Y of Z” snowclone growing into a new catchphrase. “X is the new Y” started to appear in fashion journalism in reference to the “navy blue of India” quote. In the late 1970s, various colors became “the new neutrals;” in the 1980s they were “the new black.” Today, Google gives 16 million+ webhits for "is the new". “As Gawker said, the thing looks unkillable.”
Edited 27 Mar 2008:
Nancy Friedman collected some recent citations from the San Francisco Chronicle for me:
“Happiness is the new black.” — Jon Carroll: http://www.sfgate.com/cgi-bin/article.cgi?f=/c/a/2008/03/27/DD9VVQAVO.DTL
“Obama is the new black.” — Nice twist! Quoted in Leah Garchik’s column: http://www.sfgate.com/cgi-bin/article.cgi?f=/chronicle/a/2008/03/26/DDMKVPJT1.DTL
“Coffee is the new wine.” — Quoted in Leah Garchik’s column: http://www.sfgate.com/cgi-bin/article.cgi?f=/c/a/2008/03/27/DD7AVQ5LT.DTL
The Snowclones Database 
http://www.huffingtonpost.com/2007/07/06/shafer-green-is-the-new-_n_55234.html
Found by Chris: http://www.flickr.com/photos/hober/1107825763/
Just discovered this unappetizing example in the Nov. 2006 Atlantic Monthly: “Bacon is the new chocolate.” http://www.theatlantic.com/doc/200511/better-bacon
Oops: Make that November *2005*.
new morph: X is the new X. Seen on a billboard in Coventry rail station, an add for a MasterCard product:
Cash is the new cash.
http://www.boston.com/bostonglobe/ideas/articles/2007/12/30/the_new_new_things_of_2007/
This appeared at the end of Monday’s episode of “The Big Bang Theory”.