To me story is an important factor, but it can never make or break a game. If the likes of FFVI, Xenogears and Metal Gear Solid had shit stories, I would still love them.
Gameplay will always come first IMO when I'm judging a game. This is clearly illustrated by my opinions on the Final Fantasy Tactics series, all which are fantastic SRPGs. In case you aren't aware the original FF Tactics has an incredible story, among the best in any game, while the 2 recent instalments, FFT Advance and FFTA2 have shallow crap stories. Despite the originals far superior story, I think the more recent games are moderately better as their gameplay and everything else (maybe apart from music) is easily superior IMO, such as the removal of random encounters, the fixed camera angle, a far improved skill learning system and the statute system. Story is nice, but comes second to other factors when playing a game.
