Reference-work coverage of the construction
Nigel Rees, A Word in Your Shell-like (2004) has this entry for the generalized phrase:
—— is the new —— Phrase format of epidemic proportions since 1998. Probably a development of the next phrase format (below). 'Why soup is the new sandwich' — headline in The Independent (6 November 1998); 'The 1990s are the new 1960s' — The Sunday Times (8 November 1998); also observed about this time on the front cover of a DIY magazine: 'Sex is the decorating.' During TV coverage of Royal Ascot in 1998, the phrase 'Grey is the new black' came up, at which Eve Pollard may have quoted Lady Mountbatten who used to say 'Pink is the navy blue of India'. However, in March 1974, Cecil Beaton quoted in his diary, Diana Vreeland as having said; 'Pink is the blue of India'.
which is followed by this entry:
—— is the new rock'n'roll Phrase format from circa 1993. Originally, 'comedy is the new rock'n'roll'. In Britain at that time, such was the attention paid to comedy performers and writers in the 'alternative' and 'improvisational' fields, and such as the wealth and fame accrued by young comedy practitioners in the media generally, that the parallel was drawn with the exciting, fashionable phenomenon of an earlier time. The phrase made an early appearance in The Guardian (19 October 1991): 'In this age of CDs, Discmasters, videos, prototype virtual reality, handheld computer games, all-night raves, and stand-up comedy as the new rock'n'roll, the gig has become a tedious anachronism.' 'This year's award recognizes the way the arts can reach out and extend into new areas and to a new audience. For many who have seen it, the Citizens' Theatre production of Trainspotting is a reminder of how powerful drama can be. Trainspotting proves that theatre can be the new rock n' roll' — The Herald (Glasgow) (21 May 1994); '"Gardening is the new rock 'n' roll. When I was little, it was all fuddy-duddy Percy Thrower. Now it's very social and very, very fashionable" — Ex-supermodel Ali Ward, who has switched careers to become a model gardener' — The Independent (13 June 1998).
Meanwhile, Paul McFedries, The Complete Idiot's Guide to Weird Word Origins (2008) offers this take on "X is the new Y":
X is the new Y
The idea behind this SNOWCLONE is the belief that some new thing "X" has become more popular than or has replaced some older thing "Y." The origins of this cliché go back to the 1950s, when Vogue editor Diane Vreeland commissioned the fashion photographer Norman Parkinson to do a shoot. In one picture, Parkinson shows a model in a pink coat beside a pink elephant. Vreeland's comment was "How clever of you, Mr. Parkinson, also to know that pink is the navy blue of India." This more complex "X is the Y of Z" formula gave way in the late 1970s to "X is the new neutral," which was very common for a time. That paved the way for "X is the new black," which dominated the fashion world in the 1980s. Now we see the general "X is the new Y" structure, and it's everywhere ("40 is the new 30," "Knitting is the new yoga," and on and on). You may recall that the tagline of the 2004 movie Ocean's Twelve (a sequel to Ocean's Eleven) was "Twelve is the new eleven." Apple marketed the iPod Shuffle by declaring that "Random is the new order."
Max Cryer, Who Said That First?: The Curious Origins of Common Words and Phrases (2010), however, says that Vreeland made her remark in 1962. She was certainly widely known by 1973 to have said it because the December 17, 1973, issue of New York Magazine quotes her to that effect:
Her penchant for pronouncements—"Pink is the navy blue of India," "Navy blue is the black of evening"—is legendary.
Another contributing source from the 1970s
McFedries's story about Diane Vreeland, if accurate, puts the origin of "—— is the new ——" in the 1950s and in the fashion industry. But the music industry did its part to promote the phrase as well—and from a fairly early date. Rees's entry for "—— is the new rock'n'roll" may account for UK usage of the phrase, but during the 1970s and 1980s in the United States asserting that various bands "are the new Beatles [or Rolling Stones]" and that one or another solo artist "is the new [or next] Dylan" were almost stock expressions. Google Books searches turn up several such statements from the 1970s. From Time magazine, volume 106 (1975) [combined snippets—not visible in snippet window]:
"I am not saying the [Bay City] Rollers are the new Beatles. I am saying that they are the biggest phenomenon since the Beatles."
This week the Rollers will make their U.S. television debut on the kick-off of ABC's new music-variety series Saturday Night Live with Howard Cosell. The five-man band will appear from London via satellite doing three typical songs: Bye Bye Baby, its first big hit; Give a Little Love, its current British chart buster; Summer Love Sensation, a new item.
From Nic Cohn, "Roller Ball," in New York Magazine (November 1975):
Who are they [the Bay City Rollers, again]? According to their publicity machine, they are the new Beatles; the next great teen-age insanity. Already, within the last two years, they have conquered Britain, Australia, and most of Europe. Now the only dream left is America.
From New Times (1975) [combined snippets]:
You have undoubtedly heard that Bruce Springsteen is the next Dylan; forget it, this man has his own moves. Both his lyrics and his music are wild syntheses of everyone from Dylan through Curtis Mayfield, the Shirelles, King Curtis, Van Morrison and Dyke and the Blazes. The band and the man cook and sizzle in a way I'd almost forgotten existed.
And in a chapter on rock'n'roll happenings of 1973, Will Hermes, Love Goes to a Building on Fire: Five Years in New York That Changed Music Forever (2011) offers this description of a New York Dolls performance on December 19, 1973:
At the late show, however, after Ahmet Ertegun and the other industry folks left, the band played an awesome set. "Dolls are the new Rolling Stones," Patrick Carr typed breathlessly for his column in the [Village] Voice. "Dolls are the best New York City band in a decade."
So at the very least we have documented evidence of multiple instances of the wording "—— are the new ——" from the period 1973–1975. Without pursuing the question further, I suspect that those early music-industry instances may have evolved from the related "—— is/are the next ——" which in turn may have evolved from the expression "the next big thing." Instances of that phrase go at least as far back as the January 1913 issue of The International Socialist Review, which predicted that the next big thing was not the Great War but "the Lyceum."