I don't believe the discussion is really whether or not video games are art, it's moreso whether or not they can produce emotional or deeply intellectual experiences in a way that is completely unique to the medium. Many games are unfortunately post-modern to a fault in this respect -- how many games have you played wherein you were doing something ultimately emotionally insignificant such as battling monsters and getting all the intellectually stimulating parts in the cutscenes ala Xenogears, for instance? Or where you progress through a game and all of the instances which have impact are unavoidable in the linear progression of the game so long as you don't die before you reach them ala Half-Life or Rez?
As much as I love all of the games mentioned, and though they are in fact art, they're not effective uses of the medium in terms of creating an emotional experience in and of themselves. I have an emotional connection to Sonic the Hedgehog because it was the game that got me hooked on the medium and Final Fantasy VII because it literally taught me how to read, and provided me with a very deep emotional experience -- but those things root from nostalgia, not from the video games providing me with something that cinema is more than capable of on a story-telling experience. Final Fantasy VII makes compelling statements about environmentalism, spirituality, individuality, psychology, sacrifice, et cetera -- but it progresses like an awkward movie wherein the film constantly freezes up and you have to do little mundane tasks to keep it moving along -- it moves to the same, single conclusion. I think people have a problem when debating this to rely on factors that have moreso to do with context than actual gameplay...
For instance, I could say that Sonic the Hedgehog makes a striking statement about environmentalism because it's essentially nature (a hedgehog, a member of the natural world) bringing down the negative effects of humanity (Dr. Robotnik, who builds massive polluting factories, turns natural entities into machines, et cetera) -- and the inevitability of mother earth conquering the temporary structures of man over time. But I would've gotten that from the story in the instruction manual (which is a completely different medium), from ideas I had construed primarily on my own accords, and since the progression of the "story" is entirely linear, it could have been communicated just as well as a film without any impact being made on the delivery of the message.
The only video game I've ever played that managed to communicate a message in a way only a video game could communicate it that progressed in a linear fashion was Ikaruga, and that was simply because the gameplay lent itself to the context. For information on that, read this: viewtopic.php?f=1&t=19187
The real bread and butter of the "video games are a legitimate and unique medium of artistic expression" argument are games that offer choices that reflect on the player in a personal way. If you watch a film an watch a man talking to a fish with a man's head and telling him random facts about himself and receiving incredulous responses, you might come away bearing Seaman's message -- "No matter how strange or different someone may seem to you, remember that you're just as strange to them". This message is completely amplified and made more personal when YOU YOURSELF receive Seaman's judgement of YOU -- ACTUALLY YOU. Not sweeping statements about the human race, but about specifically you -- and you know that his judgment is legitimate because you gave him the information about you yourself -- these aren't presumptions made about you, they actually are you based on the information you provided. And because of this, not only does everyone come away with a different emotional experience from the game, they come away with a markedly different PHYSICAL experience -- literature and film can offer a different emotional experience for different people despite their linearity, but not a different PHYSICAL experience -- the piece itself is a single static entity, unlike video games wherein the manifestation of the piece in the physical realm is dynamic.
So Seaman is a fantastic example of the medium being utilized to express a deep concept in a manner that no other medium could through non-linearity and choice. Ikaruga is the rare example of a game that is more powerful for its interactivity despite its linearity. And you have your Mass Effects, Black & Whites, and so forth.