Obviously this is a highly subjective topic, but I personally think that gameplay is far, far more important than story. What sets videogames apart from other mediums is their interactivity, i.e. the gameplay. Story helps to round out an experience but it's certainly not necessary for a good game. There are many games that are light on story but strong on gameplay that are very good games. There are far fewer games that have a story good enough to overlook the gameplay.
Take for example Heavy Rain. Lauded for it's story, but not it's gameplay. Tons of QTEs and, at times, excruciatingly slow game action did little to endear it to gamers. People came for the story to be sure, but the game itself wasn't that good. Once I finished it once I had no desire to play it again, even for the different endings. There's just wasn't enough gameplay there to warrant a repeat playthrough.
On the other hand, a game like Street Fighter (any incarnation, really) has a pretty dumb storyline. I bunch of people fighting each other world wide while at the same time battling some weird shadow corporation? It doesn't make a ton of sense, but it doesn't matter because the gameplay mechanics are so deep and absorbing. No one cares about the story, but we keep coming back game after game, year after year to play multiple versions of the franchise.
Story can take you only so far, but can rarely carry a game that's bad in other areas. Gameplay on the other hand can make you forget all about a bad, weak or non-existent story.
Story definitely has a place within videogames, but if it comes at the expense of gameplay, you're in the wrong medium. If someone really wants to tell a story, film or prose is far better at doing it than games are. Stories are too easily sidetracked, broken or ignored by players. Looking again at a game like Heavy Rain where some of the plot points become nonsensical due to player actions it's clear that allowing the player to have an affect on the story can ruin the story as the author intended it.
Without good gameplay, a video game is nothing more than a narrative with a shitty, annoying or awkward means of progressing the story.