If you ask me, if every video game company stopped making stories, I'd be pretty happy.
It's nice to know what's going on, but I find it better to write your own story for a game. Remember Kung Fu, Elevator Action, and Urban Champion? They didn't have a plot. Everyone made their own.
If Mario didn't tell you anything but what to do next and hints, I'd change Bowsers name to Raptoricus and change the story from "damsel kidnapped by bad guy" to "damsel attempts to divorce from her ugly obese excuse for a husband because he just sits there and watches TV in his over protected castle. Husband gets angry and sends her to a dungeon. Coincidentally, two italian plumbers who still haven't learned the alphabet start following a trail of walking muffins, turtles, and giant guns through lands, sewers, and castles that end with a clone of Raptoricus who is dropped into lava and some malformity thinks that there here to get the princess and tries to tick them off each time they are found. Eventually the plumbers get to the real Raptoricus and throw him in the lava. They then proceed to find the princess who has gone completely insane after sitting there for so long and out of that insanity gets the hots for the fat one." Which one is more interesting? The one the game has or mine?
I don't think Mario games need a story. If I know what I'm doing, its boring. But if I make it up as I go along, its more fun. But its different for each game actually. In Mario or Pitfall, it gets repetitive so I spice it up with a little bit of story in it. In Zelda or Final Fantasy, the plot is always somewhat gripping. I often have trouble rewriting something like Twilight Princess or Okami.
Basically, Mario games should avoid stories as if they are drugs in my opinion. Unless we're talking about the RPG series. RPGs always need a plot.