I think the big thing is living up to the selling point of the game. Certain genres demand excellent storytelling, while others don't. I've yet to see a fighting game with an inspired storyline and believable character development, but it really doesn't matter. RPGs on the other hand aren't worth touching if they don't have a compelling story to them. With adventure games...things get a bit dicey.
I think that Nintendo has gotten away with a lack of a story in some games for a little too long now, as everybody probably agrees that games like Zelda and Starfox could be elevated to a whole new level if they treated it with care and told a great story with the characters as is expected in most games. Don't get me wrong, I enjoy Nintendo games, but some of them could use a little more effort in terms of a plot. Part of me always wanted to see Peach develop feelings for Luigi and the final battle not be against Bowser, but brother against brother. Then again, such a move could destroy the soul of the game, like what happened to sonic. It's a tough call, but if Nintendo really wants to tout their innovation, they should toss in some character development rather than rely on the tried-and-true formula.
