Gee. I've nearly run out of things to say about this topic, as I have already gone over it over 9000 times. Let's just say that in order for me to properly escape from my real life story, which sucks arse, I'm going to need a darn good 'fake' story. I helps to be given a reason to give a damn about the characters I play as in [Action-]Adventure games and RPGs. I want to feel really motivated to defeat the villain who killed the main character's parents, or to help the orphaned main character find the value in his existence. I want and need believable, relatable characters and awe-inspiring, immersive settings: the perfect escape. All of these things can only be delivered in a great plot. Though it also helps if the story isn't entirely cliché or too predictable; that'd just agitate me to no end.
However, while a great story is important, it isn't the 'be all, end all' in all of gaming; gameplay is equally as important, for me personally. In order to enjoy my escape ("fake story"), I need my player characters to be responsive to the controller inputs. I need to be able to interact with the various in-game environments, puzzles, and characters properly. I don't want to mistakenly cast Fire on a Fire Elemental because of some odd, roundabout, and/or clunky input scheme. This is why a great control scheme is really important, especially in Fighting games. Gameplay in general tends be to extremely important in Fighting games overall.
To put it simply, I need the two aspects—gameplay and story—to go hand-and-hand in order to enjoy the great escape. This is exceedingly important in two of my favorite genres: [Action-]Adventure and RPGs, the latter of which is kind of designed to be plot-driven. So there's no "Story Vs. Gameplay" here. In Fighting games, however, gameplay trumps story, but a great story mode is always a welcoming bonus (thanks Blazblue).