I was thinking about this and honestly I don't think I personally need a story to play a Mario game. Playing Super Paper Mario made me realize this. Way to much talking in that game, and I started to understand why Mario games have never had too much story, its to keep the amount of Dialogue to a minimum. I think a good Mario game really only needs a story line capable of giving you some clear goals, although I am sure they will go a bit farther than that.
In the end the story takes a back seat to gameplay for me and I have no problem with a good storyline as long as it is not to intrusive to the flow of the game.