I enjoy complex stories in games, yes, but not if they're overly convoluted. Deus Ex, Planescape Torment, Half-Life 2 all have relatively good stories. However, I think in games it is less important how good the story actually is but how well it's actually told. The interactive nature of games opens up far more ways to grip the player than just movies or books where you're that bit more distant from the story.
Take Mass Effect 2 for instance. The story is simplistic at best but the interaction of the characters and your individual effect on your own "player story" makes it that bit more involving. If a film or book came out with the same story it'd be generic as hell.
Half-Life 2 Ep 2 as well, where after having complete control of your character and able to influence (or at least having the illusion of influence) events throughout the game you are suddenly helpless and have to watch events take place before your eyes.
So yes, a complex story can be fun, but in games, it has to be told well.








