Honestly, I think everyone is missing the point about the "don't start with the story". It's not a question of story vs gameplay at all because in an ideal storydriven game the story is part of the gameplay. Story should never be a starting point because a game is something you want the player to experience, not a story you want to tell. Starting from a game mechanic is just as bad as starting from a story - you start with core experience values. One of your core experience values can be narrative, but if you're simply there to tell a story then go write a book. You need to know
how you want your player to experience a narrative (a.k.a. gameplay) before you even start thinking about what that narrative is going to be. "Gameplay comes first" does not equal "game mechanics come first".
There's a reason starting with the story is considered a cardinal sin by most experienced gamedevs, including industry vets like Chris Avellone* or Ernest Adams (the latter of which gave me a good chewing out about it in person). I've made this mistake before myself and if your gameplay is based on your story, your game will fail. Even examples of story driven games given here work this way, The Walking Dead or Heavy Rain or even Dear Esther. You think the only thing to that game is the exposition fed to you by the narrator or something? Story is simply an element of this game, an important element, but without the other experience values this story would simply not have worked (with all due respect to Thechineseroom, I'm not completely sure it works now).
For anyone really interested in core experience values, go read Mechanics, Dynamics, Aesthetics by Hunicke, LeBlanc and Zubek. Link for your convenience:
http://www.cs.northwestern.edu/~hunicke/MDA.pdf
*To drive this home, this is the guy who wrote and designed the majority of Planescape Torment.