One question in this context is just what qualifies as a story in the first place. Taking established authored forms as the standard, one assumes a story must have an organized beginning, middle and end; a dramatic arc, a climax, a denouement; it must measure up to a screenplay or a manuscript in scope, structure and gravity.
But let's assume that no story is too modest for consideration. Let's assume that any series of events one might find worth conveying to a friend constitutes a story. A story is an interesting thing that happened to me on the way home from work yesterday; it's how you met your wife; it's the events of one person's life, starting with a single-parent childhood and leading to the election of America's first black president. Scope, structure and gravity aren't necessarily important, though they may arise from the events entailed. What's important is that the story holds meaning for the person involved in it and the audience observing it-- in a video game, that's the player, one and the same.
Different games allow the player to make his own stories out of the gameworld in a variety of ways. These stories range from the humblest anecdotes to the most sweeping historical sagas. One might organize this potential as a hierarchy of storymaking in games:
Micro-level storymaking: unique moment-to-moment chains of occurence built up from the game's base mechanics. Most games that supply the player with a limited palette of expressive verbs engender this level of storymaking: Far Cry 2's gunfights, the Grand Theft Auto series' vehicular mayhem, BioShock's plasmid and weapon play, Dead Rising's plethora of implements for taking on the zombie mob, and so forth.
I decided to drive my jeep up over a hill. As I crested it I saw a group of mercenaries in the valley. I drove directly toward them and dove out of the jeep, letting it plow through the mercs just as they noticed me. I fluidly sprinted forward and slid towards the last couple of stragglers that had dodged the jeep, and handily finished them off with one full magazine of my silenced sub-machine gun. I hopped back in my jeep and continued on toward my destination.

Mid-level storymaking: exercising agency over which major fictional elements of the gameworld I experience, in what order. The gameworld is arranged at least in part as a web of potential experiences I may choose to engage with: exploring the wasteland in Fallout 3; deciding which missions to do in Grand Theft Auto; choosing how and whether to deal with civilians and the main plotline in Dead Rising; deciding whether to engage in Yakuza 2's side missions; choosing story branches in Deus Ex, etc.
I decided I was going to be the savior of Willamette Mall. While I advanced the plot's mystery if it was convenient, I would always ignore it in favor of finding and rescuing trapped civilians. By the end of day three, I'd been through hell gathering up dozens of survivors. We climbed aboard the helicopter and escaped, though the cause of the zombie outbreak remained a mystery. I'd decided that the lives of this group of individuals was more important to me.

High-level storymaking: the player determines what elements are present in the gameworld, and any narrative that happens there is entirely a collaboration between the player and the game's systems. The only fiction determined by the designer is the broad premise of the game's setting, and individual building blocks for potential outcomes. The Civilization series, SimCity, and The Sims exemplify this type of storymaking.
I decided to create a nice, tidy young man, and across town a lovely, good-natured young woman. They each advanced with some success in their respective careers, then met at a local restaurant. After a brief courtship, they married. They adopted two babies, who grew into happy schoolchildren. At this point I built a trailer in the neighboring lot, and created a happy-go-lucky slob of a young man to live there. He spent most of this time puttering around, playing guitar and looking through his telescope when he wasn't out delivering pizzas. After becoming friends with the nice couple next door, he would frequently burst into their house in the evening and humorously disrupt their routine with his wacky behavior. I'd decided my Sims would be the inhabitants of a standard network sitcom.

Note that none of these examples involve epic, expertly-crafted storylines handed down to the player by an author, or emotionally manipulative plot points thought up by a genius writer. But they are the kinds of stories that stand out most strongly in the player's mind after a game is finished. This is because video games are driven by the player, experientially and emotionally. Fictional content--setting, characters, backstory-- is useful inasmuch as it creates context for what the player chooses to do. This is ambient content, not linear narrative in any traditional sense. The creators of a gameworld should be lauded for their ability to believably render an intriguing fictional place-- the world itself and the characters in it. However the value in a game is not to be found in its ability at storytelling, but in its potential for storymaking.