Well, before answering the dilemma you've asked, you need to answer this question: what is the main focus of the game?
If the focus is gameplay, then make the system to support gameplay first then add story later. This is bottom up technique.
If the focus is story, then make good story first then make gameplay system to support the story. This is top down technique.