Personally, I will say that it depends on the story. It all depends on the idea, and in what medium would it fit best. Perhaps longer, more elaborate stories are best told in games.

I will second Dragonheart here, and say Assassin's Creed is a great story, although I'm focusing more on the first one here (since I've only just finished it, and am now playing ACII), the merger of two stories; that of Desmond Miles in present day, and that of Altair in the past. Both characters are involved in two good story lines (although, obviously, Altair's side of the story is a bit more elaborate). The story telling is very thorough, doesn't leave any unnecessary holes in the plot. It's an exciting story, one that draws you back to it, to find out more about these characters, and why they are doing what they are doing etc. To me, that is the key element in telling a story. You need one that makes the reader, watcher or, in this case, the player care about the characters. And I believe a story such as this could have only been told in a game.

I believe that every idea has the potential of becoming a good story. One of the key factors that make it become one is the medium.