The Game Industry likes to refer to itself as art. They like to talk about how they allow the players to have deeper experiences in the story than the player has had before. I am not going to comment on whether or not games count as art (I think it's subjective and on a case by case basis), but the storytelling is an interesting aspect.
When a reader reads a book, they often feel strong connections to their characters. They get to hear what their characters think, feel, dream, hope, etc. It can reach a point where, if a reader is truly immersed, they feel like they ARE a character. Games give players one more step into that immersion. They let players actually BE that character. But this is a problem, because games usually have the following constraints:
1) A linear or semi-linear story
2) A path for their protagonist
3) Other characters that the player interacts with.
I'm going to use Tales of Symphonia, an RPG for the GameCube, as an example of this. Let's consider the story. You play as a main character, Lloyd, who is trying to save the world. Lloyd does so by running around, killing random monsters, levelling up, and beating bosses. Over time, he encounters other characters, which join his party. Now let's examine how the above effect the players perception of themselves as Lloyd:
A linear or semi-linear story
Lloyd really has about one goal, and he can only really approach one ending. "Defeat the bad guys, save the world." The plot is a bit more complex, but that is the overriding choice that the player makes. There are certain dungeons to which the player must go, to collect certain things, to reach this ending. The player does not get much of a choice in that; they have to follow a roughly linear, designed path to 'whats next'.
Tales of Symphonia is what I would classify as 'semi-linear'. The player can make choices along the way that effect the ending, either by effecting the relationship between their character and other characters, and they can even change the end a bit. But there are finite choices that they can make, and these are NOT tied to the gameplay. Throughout the game, the player is given several binary decisions, and based on which ones they select, the ending varies. So, the player CAN influence the ending of the game, but to do so is almost a seperate section of the game then how they PLAY the game. It does not matter how many random monsters you kill, or how strong your character is. The core gameplay is not the deciding factor.
A Path for the Protagonist
In Tales of Symphonia, the player is guided by other characters and clues as to where to go next. There are not really a ton of options, for the player must hit all certain spots, and experience certain events, before the story can advance. "Side Quests" are the closest thing to additional story, but they often include supplementary or inconsequential story, and do not actually move the key plot forward.
The metaphor that the game promotes for the path to victory does not leave the player with a lot of time to figure out their own way of creating a path to victory. They must follow the path that the game has set forth for them.
Other Characters that the player interacts with
Oh boy, this is the hardest part to tell in a story. In a book, the characters have a free range to say whatever the author wants them to say, and interactions can be as complex or simple as any scene allows. The same is true for theater, movies, television, radio, and pretty much any other drama with dialogue.
But in games, we run into a problem. The player has to interact with other characters, but we can't really create verbose responses for everything that the player can say. In Tales of Symphonia, Lloyd has his own personality and talks for the player. That is one solution, although it breaks the illusion that we are Lloyd, and it works really strange with the scenes where Lloyd gives you a choice of two different things to say. Suddenly, we are Lloyd, but normally we are not? The amount we get to shape our character is pretty minimal.
Games have handled this in a variety of different ways over the years. In the Legend of Zelda, you never see what it is that Link says, only the responses that the NPC's give. So you can imagine that Link said whatever you want, as long as it makes sense with that response. In the Monkey Island and similar series, the player doesn't say anything until the player makes a choice about what to say, and then the computer has a series of canned responses. So there is more options, but ultimately, it often results in the player trying to say everything to see what they can learn from the NPC's, even if it means taking similar dialogue paths again and again.
In the Computer Science industry, programmers have been trying to get computers to talk for years. A.L.I.C.E. is an example of a bot that was scripted, but after tons of work on ai and intelligent sentence responses and parsing, the bot could still get confused by complex sentences. While the technology has doubtless advanced in the years since, it is still unlikely that the technology exists for a computer agent who could respond intelligently to any statement the player could construct, let alone adapt that entity to have a growing, changing relationship with the player, interact with the player in non-speech methods, and then expand that to have many such characters in the game world.
So, in short, this is the biggest difficulty encountering story-game evangelists. Interestingly, a method of dealing with this was developed by Chris Crawford on a Mac game in the '80s called Siboot. Essnetially, a limited number of symbols was used to represent different things that the player could say, and so the player communicated with other characters in a symbolic manner. He gives an excellent explanation of it in his book "Chris Crawford on Game Design", which I highly recommend reading.
These are only some of the difficulties that story's must overcome in games, but step one of the battle is understanding the problems to overcome.