Well, although this was meant to be sarcastic, it has some truth in it. I remember when I played through New Super Mario Bros Wii. It felt like I was playing Super Mario Bros 3 again. Ok, that was on of the best NES games, so that is not a bad thing to say. But there was one thing that Super Mario Bros 3 did better. I wanted the flying feature back... Flying in SMB3 or in SMW was a cool feature.
Ok, so back to lack of Story. What I feel lacking in Mario Games is, that there is no real characterization. I don't know if you have ever played Ratchet & Clank, or Jak and Daxter. But these games combined fun gameplay with humorous dialogues. You played a level and then got a funny cutscene with clever dialogues. That was really a good game experience.
So after having played the J&D and the R&C Collection I have played New SMB Wii. And I really felt that there was something lacking. After each Midlevel Castle the Kooper just ran to the main castle or ariship. And after the castle the princess is brought to the next castle. That was really repetitive. They could have done something more interesting if they tried. Sure, you could say that Mario is all about Gameplay. But there are games that can combine Gameplay and Characterization and Dialogues.
I don't say that Mario should get a deep Story. But they could do better than always the same sequences after the Castle. Like in Super Mario World, where you saw a sequence after each castle and each castle was destroyed in a unique way.
Well, I do not think that I will get the WII U in the next years, after the Wii experience was a little too underwhelming for me (due to my hating the Wiimote as a controller), so I will most likely pass this Super Mario Bros U. But I would really like a New Super Mario World (without the tablet controller gameplay gimmicks) and a new Zelda-Link to the Past with eagle-view. Until that day I must admit that I had more fun with the PS2 Trio Jak, Ratchet and Sly.
On the other Hand, Rayman was also a great 2D Jump'n'run game. But its story was so bad that I would have prefered if it just wasn't there. But thats the awful truth behind this. It is really hard to create a character and a story that are enjoyable. Maybe even harder than to create interesting levels to play.