I think what Levine meant is that games shouldn't try to hide their plots from players in the same way that some movies do. Movies often operate from a god's eye perspective in which the viewer is aware of things that the characters are not, enabling the viewer to see complex connections and symbolisms.
This doesn't mean that game players are morons or that plots need to be complex, but that plots in games should be more self-contained, enabling the player to form a more personal connection with the game. "Simpler" plots are more conducive to stronger immersion.
Look at how players love Planescape: Torment or Baldur's Gate 2 as wonders of game writing. Those plots were "simple" in that they didn't actively try to deny the player information, preferring to give the player hints and nudges along the path.
He wasn't talking about not having multiple endings or whatnot, he was encouraging designers not to FORCE a player into multiple playthroughs in order just to get a satisfactory, even excellent experience. And that, in itself, puts good writing and accessibility at the forefront.
Game plots can be deep and will in every sense benefit from being so, but like any well-written piece of fiction (especially fiction that must entertain as well as inspire/intrigue), game plots should allow players to be find ways to enjoy and connect with the game at each level.
He put Half-Life up as an example of good storytelling. He's right. Half-life is enjoyable at the basic level, providing an interesting environment to explore and run through and engaging challenges and set pieces. But it's enjoyable at a deeper level, exploring characters like Alyx, the scientists, the G-Man, or the universe-level events like the 7-hour war, the border wars, or the Combine. And it's enjoyable at a still deeper level, examining Gordon's philosophical role as a messianic figure, on the "meta" level, to use the cliche'.
Bioshock does this, Planescape and Mask of the Betrayer do this, Baldur's Gate 2 does it (though on a shallower level, I think).
Levine's saying "simple" when perhaps the proper term is "accessible" or "coherent". To not be so is failure on the writer and the designers part.
While I'm suggesting levels and terms, game plots should be enjoyable on the level of "playing", on the level of "immersing", and on the level of "interpreting".
Of course, like a summer blockbuster or a "plot-light" title, a game doesn't DEMAND this kind of depth. But this kind of depth needs to be more common in order for games to advance as an art from.