Re: How do you start designing a game?
I would agree with bob's #2 post. The first step you should take is to decide what kind of emotion you would want your players to experience by playing your games. Games are all about emotions, things like story, mechanics just act as mediums to deliver these unique experiences. Whether it's the feeling of overjoyed when achieve something or the bitter sadness of seeing someone die or the fear of ghosts... Just decide on at least one for your game. Successful titles didn't include innovative ideas from nowhere, their designers also had to work on this very first step before anything else. Then, after we have some kind of emotion we want our players to feel when playing, it's time to give it some physical elements, which are theme and mechanics. This is where most designers spend their time working on the most to ensure these elements blend well with the emotion. By "blend well", I mean you have to actually be able to feel that certain emotion through "theme" and "mechanics". Don't focus too much on additional stuff like "depth" or "logic" at this step, you can do it anytime.
I hope this advice would help you somehow !