There aren’t any 1-60 zones outside of the Pandaran starting zone that aren’t at least near a decade old.
The Cataclysm revamp wasn’t even, of course. Some zones got more of an update than others. Some, like Arathi are just somewhat streamlined versions of the Vanilla zone.
When it comes to zones that got the heaviest overhaul in Cataclysm horde-side, you’re probably looking at Silverpine Forest, Hillsbrad Foothills, Stonetalon Mountains, Thousand Needles, Badlands, and Burning Steppes. Southern Barrens is a bit weird to me. It did get a near full re-vamp, but the story has some heavy callbacks to the old zone, so it might not resonate with a new player.
Silverpine and Hillsbrad got great story updates, but they also did a fair amount of experimenting there with tech and such, so there can sometimes be some buggyness to deal with.