Stories? Of course you need your basic story structure and to consider how immersive your storyline could be. I feel a lot of games are weak in terms of plot, but that's me.
One way to put an effective plot-line is to:
Make the audience ask a question, the audience will want to find out the answer. But one question isn't enough, you got to make twists and have the answer turn in interesting ways - unexpected or just answer the question with another question.
Of course when coming up with ideas they need to flow realistically, appear convincing (even if they're far-fetched) and be consistent.
Ideas themselves always start at one point and elaborate - a story I'm writing at the moment (not a game) started simply with the idea of a person in a frozen wilderness lost. I asked myself "Who is this person? where are they from? how did they get here? and 'Where are they going?" and it of course has developed into something I like.
For a game, they can like any story, but they of course need to bear in mind - what you are capable of and whats works with game play, I mean if you were to imitate a Jane Austin novel into a game it would work, but something like Lord of the Rings does.
I'd also say, please, no cliches (it's really doing something that's been done over and over, if it's what you're really like, then it's up to you of course), if I see another FPS to do with unethical experiments of humans, humanoids or something superntural going terribly wrong - so now that you are left to destroy super creatures, then I'll scream.
Might also help trying to do 'idea chains'.
Tropical Island->Crysis->Start again->Tropical Island->Hawaii->Tribes->Tribal Religion->Worships->Gods->Mythology
This could be the start to a game idea based on Hawaiian mythology, dig deeeper into some research in Hawaii and the idea chain I just started couple turn into something interesting - then you can start adding your characters, what their aims are and what the problems are etc.
"Experience never provides its judgments with true or strict universality; but only (through induction) with assumed and comparative universality." - Immanuel Kant