Let me give some context. Three of my friends and I have a pretty good game idea cooking. It's based off of a prototype I made that's evolving into a cool game mechanic. The mechanic itself is a toy that's fun on its own, but we haven't designed any puzzles around it yet. We have a design document going, and we are answering a lot of questions about what's in the game.

It's become clear early on that everyone (including myself) likes the characters and the story a lot. Considering what our favorite games are, this is unsurprising. A story driven game makes sense to me. I like the emphasis that Paper Mario: The Thousand-Year-Door, Portal 2, and Tomb Raider place on story, and I imagine our game will have a similar feel (lots of dialogue, plot twists, lovable characters).

However, one team member raised this point in the design doc:

I am feeling like [fleshing out the story] is our biggest hurdle right now for making more design decisions - like more specific decisions about levels etc. Is this true?

I am uncertain about working on the story extensively before gameplay, and my uneasiness was reinforced when I read this question about story vs. gameplay.

What I want to say is: "Let's continue to work on the story, but also start brainstorming and prototyping abstract puzzles and combat sequences, and we'll creatively match them together later."

Is this a reasonable approach? If so, how much of the development of these elements should be done independently? Should I try and create a whole bunch of puzzles while my other teammates focus on story and aesthetics? Then when we have a lot of story and game 'chunks' we can match them with eachother to build something meaningful. Or should we focus on iterating individual levels as distinct units where puzzles, story, etc... are designed together? Or maybe we need to put our excitement about the story on hold and just focus on gameplay. Is there another approach to design that we can take? Am I missing something crucial?

I have discussed story and gameplay because they seem the most likely to be at odds with each other, but we also have to consider user interface, music, art direction, etc... Can we design these independently as well?