You know, Mario was a plumber who went to save a Princess... that was kidnapped. And he is the one to go... for no reason!
Back then, that was as MUCH cliche as it is now.
But it makes no difference. Mario was one of the greatest hits. The second was Sonic.
There was that debate back then.
"Nintendo or SEGA?"
Nintendo of course won the race, since SEGA was more arcade and action than deeper variety of games.
Still this question was really a debate about "Mario VS Sonic".
Sonic had more entertaining games, action, cool graphics, speed....
Both were challenging though.
So a SUPER cliche story was the story the killer app for Nintendo was based on.
There you go! A live example.
What you must focus is innovation.
There is an artist school (I dont remember the exact one but it exists)
that believes that in order to make something worthy, you must be very influenced by at least a masterpiece already made.
They consider this as high form of art, since it needs a lot of education to get properly influenced by a masterpiece of the past.
So what do these weirdos say here?
Get inspired by something, make something like that. DON'T COPY IT though... make something original.
For instance:
Three pigs make houses. One with hay, one with timber the last used stone.
The wolf destroyed the two first so the two pigs went to the third one, and were saved cause the third's hard work was worth it.
You know the fairy tale.
Now look!
ACT 1:
Three brothers divide their wealth they got from their parents equally.
Then they go on with their lives.
ACT 2:
The first one lives in luxury and has women and expensive stuff.
One day something bad happened that influenced most of the people, like an economic crisis and he is broke now.
Seeks his brother now.
ACT3:
The second brother saves some money but does the same thing as the first one.
So the crisis hit him hard too.
Act 4:
The first two brothers unite together.
With the second's savings they do a trip to find their only hope.
The third brother.
The third brother succeeded, cause he invested the money wisely.
EPILOGUE:
So he takes them in his company and everyone lived happy ever after (or whatever people say in English to make a story conclusion). :p
Boom! in 5 minutes, from a fairy tale, a catchy story.
Is it cliche? HELL YEAH! But it's not that bad isn't it?
Stop worrying about something. Instead, substitute feelings of worry with feelings of hope.
Hope drives people do things, while worrying makes people numb. ;)
Don't overdo it with hope though. ;)
EDIT:
P.S.
Not to mention that you HAVE to write a few bad stories in order to become a good storyteller.
Doing nothing or avoiding stuff will get you nowhere. free your mind and who knows?
You might find a great idea. Imagine it being shown in a movie... you got that?
Ok now instead of a movie, make it happen in a game. You are the story author AND the director.
So go now and make something that it is worth our time to play it.
And bring it here so we can all together cherish about it.
Want a piece of advice?
How about how do I approach the problem?
Programming methodologies.
You got the big problem "A".
What do you do?
You split it in smaller problems.
a1, a2, a3, a4, a5, a6, a7, .... , ai
a1 is easy to write code to solve it.
So you write the code.
then you go for a2. It's harder.
We split it into two pieces:
a21 and a22
Are these easy? Yup!
So you write code for both, thus a2 is ready too.
........
and finally you do the same for ai
Everything was split to small easy to solve problems.
Every small problem was solved.
Now combining all these parts....
you got the solution for the big problem A!!!!
Now imagine that A is the problem of a good game story.
First you learn to make small stories. How? PRACTICE!
Then you learn to make better small stories. How?PRACTICE!
Then you learn to make good small stories. How? PRACTICE!
Then you have learned make incredible small stories. STOP PRACTICE!
If you don't already have the materials to make your game after so much practice,
just use your polished skills to make small stories, merge them together and make a good game.