Take board games or sports games, for example. They've been around since the earliest years of civilization. We have played them all that time, but never drew a comparison between them and art like what a painter or musician would produce.
Yet, suddenly it became a debate when we got to video games because we could start inserting all the other art mediums as desired, while still retaining the interactive, unpredictable nature of previous games. And so we go out on this mindless quest to find the most moving games we have ever played and show them to the critics.
I think that what this suggests is that we have to either expand our definition of art to include all the interactive forms(including toys, board games, and sports) or define two kinds of art - the interactive, and the authorial - and view them as complements to each other.
Don't tell me that the surreal landscapes of NiGHTS into Dreams weren't art-- I spent many hours as a kid exploring every nook and cranny of those levels all while trying to run away from the dreaded alarm clock. The start of the fourth level of NiGHTS forces you, the player, to make a choice that ultimately draws you into the game even more-- you must trust that you have enough control of your environment to jump off of that cliff and fly. Don't tell me that there isn't art in that beautiful moment when you realize that the rules of the game have changed so beautifully.
Anyone who has played Metal Gear Solid knows how Psycho Mantis' blurring of the fourth wall stretches how you think of playing the game. You, the player, have to make a physical action to get through the battle. Throughout the rest of the game, you are continually making choices about how you get through each challenge-- choices that other characters are aware of and will react to. The impact, ultimately, of such choices is that you empathize with Snake in ways that would not be possible in any other medium.
Others have given many other good examples, and will undoubtedly continue to do so. For my part, however, I will be content to share my 2¢ on the matter and to point attention to this important conversation.