One can get analytical and academic and discuss lots of increasingly theoretical details and structures, but it's really actually about that simple. And whether your story resembles "Pride and Prejudice" or "No Country for Old Men", it's pretty much going to have those elements. I repeat: Characters, with Goals, Struggling to Achieve them. That's been the basis of a good story ever since Og first regaled his fellow cave dwellers with how he opened a crock of whup-ass on a sabertooth tiger.
But if you want to look at this from a game developer/designer's point of view, you might think about doing a bit of mathematical substitution:
Characters = Player-Avatars
Goals = Objectives
Struggling = Gameplay
Achieve = Rewards.
Which gives us this:
"A game story is player-avatars, with objectives, using gameplay to achieve those objectives (get rewards)."
Okay, it's not Shakespeare. But it's something. And it actually gives us an interesting look at where traditional story and this whole newfangled game thing might have some basic building blocks in common.
Which begs the question: "If it's that simple, why doesn't it work?"
There are a few reasons, I think, but I am by no means the first and last authority on this.
They are often 2D paper doll imitations of well-known stereotypes. If a character is predictable, it's hard to get too fired up by her problems. See the comments to my previous Gamasutra blog post for some good thoughts on this.
What the character wants might not make sense, or might not be realistic, or, on the other hand, might have been done in a much more direct and simple way if there wasn't a lead designer involved... Besides, since the goal is generally "Save the World/Universe/Species," it often lacks interest. Goals are too often epic, but not personal.
It's not unusual that the story occurs in parallel to and independent of the gameplay -- the classic set-up of lots of gameplay, then a cutscene where other things happen that advance the story. While the gameplay unlocks the story, it doesn't always drive, enhance, or enrich it. Necessarily, the story equation starts to fall apart. If what the player is doing isn't the story, we no longer have one.
We're usually pretty good on this one. Whether it's rankings, virtual gold, cutscenes, bragging rights, or power-ups, one thing you can guarantee is that success is rewarded. However, if it isn't tied into the struggling and the goals of the character, why should the player-avatar care?
So though the definition appears deceptively simple, there seem to be a lot of weak links in the way that we execute it.