First, I think that it's really important to define terms in a discussion like this one. One central term is literacy. Are we thinking of literacy as being able to decode symbols to create meaning (functional literacy) or are talking about literacy as the ability to understand, critique, and question text, media, or other things interacted with (critical literacy)? Or are we saying the ability to read and comprehend books (print literacy)? Another central term is video game. Is the discussion around "mini" games such as Tetris, MarioKart, BrainAge, or around "complex" games, games that require players to take on a new identity, play for more than 10-100 hours to complete the game, problem solve and face consequences for their decisions, such as Final Fantasy, Spore, Sims, DragonQuest, etc? (BTW, I borrowed these terms from Marc Prensky, who talks about them in his book Don't Bother Me Mom, I'm Learning.)
From the reading and studying that I have done, I think that complex games can probably improve critical and perhaps even functional literacy. James Paul Gee makes a case for this in What Video Games Have to Teach Us About Learning and Literacy, in which he argues that educators can study games to observe extremely effective teaching techniques. (Whatever you think of the content of games, they are very good at both motivating people to keep playing them, and teaching them an internalized implicit set of rules so that they can understand and play the game.) One example of Gee's arguments about how games can support even print literacy (there are many, and I really encourage you to check out his book if you are interested!) is that games teach players "to learn about and come to appreciate interrelations within and across multiple sign systems (images, words, actions, symbols, artifacts, etc.) as a complex system, [which is] core to the learning experience." To paraphrase, learning to read at its most basic is really a process of learning how to decode and understand a symbol set. While games may be teaching players to understand a different kind of symbol set (not the English language), they are honing the same underlying skill.
In addition games provide a unique chance for players to immerse themselves within narrative structures, becoming part of the story creation itself. Some games have better stories than others, true, but they also do something that books can't (even Choose-Your-Own-Adventure books!): they give the "reader" / player agency and power over shaping the story line.
Finally, I'm borrowing from Steven Johnson's book Everything Bad Is Good for You to make this little chart about the differences between books and video games. While books do many things very well, and we have invested them in Western culture for hundreds if not thousands of years because of the things they do well, video games do other things very well, and I don't know that it has to be an either/or dichotomy. Maybe print literacy is not the main benefit of video games, and maybe it shouldn't be. But perhaps there are other, just as valuable, skill sets that video games have to offer. Take a look and see what you think.