We don't need a great story in a game but the fun factor. For good stories we have movies. Games these days are becoming more story-oriented rather than providing us with the fun factor. Take Wanted:Weapons of fate as an example. Nice story but dull gameplay that gets insanely repititive.
I resent that point. A good story is the heart of any game, as it is for a movie. You feel Wanted has a good storyline? Hardly. It's merely a small extension to the original movie, which was even more suckage.
Remember Kane & Lynch: Dead Men? Of course you do. You just completed it, right? What was so compelling about that game? It's gameplay? It's physics? weapons? graphics?
The answer is it's storyline & the character development. Remove that and all that you have left is a run-n-gun game. The only thing that kept me playing (and completing) that game for 6 hours straight, was it's story. I was amazed how grippingly each emotion was portrayed by both characters. Remember the point where Mute kills Kane's wife & Kane lashes out on him with a shovel saying "You should have let me talk to them!" & continues beating him down to pulp? Yes, that was a epic moment.
That is how much a good story is essential to a game as is it's other aspects. Why do games like Prince of Persia, God of War, Max Payne, BioShock, Fahrenheit etc. get so exciting that they demand sequels? It's not just their gameplay, not just their graphics, but it's their story.
Pay attention to the detail in BioShock. It will baffle you as how intricately they have designed the underwater city, Rapture. You'll start off without knowing who you are & where you are. As you progress, you'll realise (through various conversations & audio logs) about the storyline unfolding. The game is an art. You'll know how important a storyline is for making a game immersive enough.