I agree that Hyrule Castle and Saffron City were awesome. All of the SSB Stages(minus Congo Jungle) were perfect(for the most part) and very fun. Congo Jungle on Melee seemed to be much more fun...compared to the 64 version mostly because it was the most boring stage in the game.
Anyway, Yoshi's Story was STILL the worst choice to bring back since it was already redone in Melee as a stage. That one should've been replaced, but the other stages were well done.
As for returning stages to Brawl? Hyrule Castle/Temple, Final Stage(called Final Destination on Melee), Fighting Polygon Stage(remade to be Battlefield), Peach's Castle(the Melee variation wasn't bad, though), Mushroom Kingdom,(not the two crappy remakes. Most agree that the 64 version was MUCH better and MUCH more fun) and I actually liked Brinstar Depths and Congo Jungle, IMO.