I'd also say the two are interlinked in the case of computer games to be honest, since the gameplay defines, to a large extent, how involved and enjoyable the story is. but, not so much a bad storyline, but a poorly executed one, can ruin it.
For me, I find wooden-sounding voice acting will kill a game for me very quickly, I can cope with low-range graphics, but if there's talking in the game, for God's sake, don't make it sound like it's being read from a blackboard by a Russian manic depressive. I prefer text to bad voice acting, possibly that's my audio background kicking in there though.
I'll say this though, a good story is more likely to make me tolerate bad gameplay, purely to find out what happens, but I'm not sure that would make it a good game, successful, certainly, but a good game needs to be able to balance the two, so the gameplay makes you feel you are participating in the story, and not simply trying to get to the next bit, and the story itself is compelling enough to make you want to get to the next bit.
The Morrowind series is a good example of balancing the two, whilst it's fun to perform the storyline, which is, as a whole, quite a good one, there's a lot of unrelated stuff that you can do purely to exploit the gameplay, and it's quite fun to do even with the storyline waiting for you to get back to it.