First, from a math/logic perspective, video games are a super set of all art (save taste, smell, and many touch aspects). Practically any piece of art that has ever existed can be experienced through a video game.
Example 1. Paintings -> Textures. Sculptures -> 3D models. {Books, Movies} -> {Plot, Storyline, Character Development, Text, Conversation, Setting}. Some touch -> Force feedback. Music -> Soundtrack. Sounds -> Sound effects.
Second, video games can be "turned into art" by trivial means.
Example 2. Imagine the Mona Lisa was never painted. Some game designer creates a maze game with colored walls that allows zooming in and out. If you zoom out enough, the level is shown to be the Mona Lisa (to any degree of fidelity required). This is not art, but printing off a copy and taping it to your wall would make the printed copy art?
Example 3. Imagine that someone's play through of Final Fantasy X is recorded. One in which he talks to everyone to provide the character development, etc. This is essentially a (super long, rather slow developing) movie. It has a plot, character development, etc. This movie would then be art, but having any say in the outcome is not? (FYI, I do not intend to compare FFX to the Mona Lisa by this example, it is merely an example....any sufficiently interesting game would have worked. I mainly chose FFX because I remember some critics calling it a 100 hour movie because of the long cut scenes)
Example 4. Imagine a given work of classical music was never created. Imagine a platformer in which the only solution recreates this work through sound effects to reach the next area. A given audio recording would be art, but the game itself isn't?
Third, having some extra control in how you experience something should not change whether it is art.
Example 5. While watching a movie, I may, intentionally or not, fail to notice something a character says or an object shown on the film. It is still art. If the movie from example 3 were to skip some of the character development, it would simply be a movie with crappier character development.
Example 6. You are reading a book and do not recognize why certain elements are crucial to the plot. In a subsequent read, you put 2 and 2 together and notice what you didn't before. In a game you can find side plots you didn't know exist that explain further why the plot turns out as it does, or even simply "finally put 2 and 2 together."
Fourth, having an objective/puzzles should not disqualify something from being art. (a.k.a., BRAID IS ART...Grrr)
Example 7. "Where's Waldo?" books.
Example 8. "Choose your own adventure" books.
These two examples can be done with works of arbitrary quality and I'm sure could be qualified as "art." Not only this, but these can be directly made into video games.
All art is the expression of some idea or emotion {or combinations} by it's creator. How can a medium that allows so much more than any other medium not ever have the possibility of yielding art?
I have the impression that Ebert wouldn't give a video game a chance anyway. I doubt he has had much interaction with the medium of video games, and, as some posters above have stated, may have an agenda against the medium as a whole to protect movies or is biased another way (perhaps just age). You cannot judge a book by it's cover, you cannot judge a movie by it's trailer, and you cannot judge a game by it's trailer either. Not only this, but just because you cannot appreciate something doesn't mean it is not art.
I give Ebert's article/argument two thumbs way down.