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:
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.