Rolled a new Undead Rogue post-Cataclysm and was surprised by the phasing and the linear progression of the story. I haven't played WoW in years and this is a nice addition IMO. Tried to roll a blood-elf and a draenei to check out if there's any of the same phasing and quests but haven't found any so far. What other races were changed in the same way as the Undead? If you could, can you tell me what the general plot of the quests are? The Forsaken quests seem centered on Sylvanas vs the Worgen.
As Raven Dreamer says, only "classic" WoW zones were updated with Cataclysm, although some experienced much more profound alterations than others. In terms of starting areas:
A new worgen character experiences the siege of Gilneas by the Forsaken, during which time he or she is bitten by one of the numerous worgen running amok in the city. Quests here focus on saving the people of your falling kingdom while coming to terms with your new identity as a half-human. This is a dramatic story with lots of phasing and atmosphere.
A new human character appears outside Stormwind and will help restore order in the aftermath of the cataclysm: your main opponents are Hogger's Riverpaw thugs and the low-level minions of the current end-game antagonists, the Twilight's Hammer. There are some fun and funny quests, but it was nowhere near as dramatic or interesting as the worgen opening, in my mind.
A new dwarf appears in an isolated settlement southwest of Ironforge and must train and prepare for the trip out of the backwoods and into the Alliance. Most of the combat at this point was against local flora and fauna, rather than major organized factions, although there are some ice trolls that have fallen in with one of Deathwing's elemental underlings.
A new gnome appears in Gnomeregan; my understanding is that it's just been retaken by the gnomes, and a new player has to deal with isolated pockets of resistance before going up against a major mechanized rebellion. Haven't actually played this one, yet.
A new night elf will explore Darnassus while learning about kaldorei culture, before beginning a very antagonistic relationship with a particular satyr, who starts you off on quite the campaign of corruption-chasing through northern Kalimdor. I enjoyed these quests, but like all classic races, they weren't nearly as dramatic as the Cataclysm-exclusive races.
The draenei starting area is still unchanged from The Burning Crusade. Draenei are dealing with the the crash of the Exodar, and their first tentative steps toward working with the Alliance.
A new goblin character is an up-and-coming executive on an isolated goblin utopia. You'll get a fast car and some flunkies and clear out as many obstacles as you can to becoming the next Trade Prince—but the Cataclysm will destroy your entire civilization and leave those of you who tried to escape stranded on an island where you'll gradually be introduced to the Horde and your destiny as their premiere artillery faction. Incredible use of drama and phasing; easily the most personal quests I've experienced. If you can stomach the playful use of anachronism and satire, this is some of the best that World of Warcraft has to offer.
A new orc has to help survey areas affected by the cataclysm and reassert orcish control of Durotar and surrounding regions. It's been such a long time since I played this that I can't honestly remember too much about it.
A new troll gets to see the newly reclaimed Senjin Village and deal with increasing tension between the orcs and the other races of the Horde, while simultaneously putting up with human coastal invaders (I'm assuming). Haven't played this one yet.
A new tauren must deal with the rift that Garrosh Hellscream caused by killing Cairne Bloodhoof, but I don't know much more than that, as I haven't played this opening yet.
A new Forsaken will learn what life is like for the unliving while trying to make the transition easier for the newly undead—including Lilian Voss, whose powers are certainly unusual. There's a lot of worgen and Scarlet outposts that you have to deal with, and a lot of tension with the rest of the Horde as you perpetuate Sylvanas's plans to chemically conscript as many human settlements as possible in the vicinity.
The blood elf area has also not been changed. Blood elves have to help their people deal with their magical addictions and the scars of the Scourge invasion.
That's all I've got, at the moment. I may be able to update with more information as I continue playing and researching.
For the release of Cataclysm, all of the base game regions were updated both in terms of the cataclysm, as well as updating quest flow, loot, possibly levels, and quest hubs.
In fact, the only things completely untouched by the Cataclysm were the previous expansion zones -- The Draenei and Blood Elf 2 starting zones, Outland, the Death Knight starting zone, and Northrend.
So in short, all races except for Draenei and Blood Elf got revamped starting zones. It's been a while, so I will defer the subquestion about quest plot to someone who has played the game more recently.