Depends...some games are just meant to be arcadey, and in those, like DMC and Ninja Gaiden, I don't pay attention to the story whatsoever.
Now, on the other hand, RPG's and blockbuster titles usually require a good story.
Rockstar: Announce Bully 2 already and make gamers proud!
Kojima: Come out with Project S already!