Well Shadow of the Colossus is truly an artistically amazing game, it is no more "art" than any other game, simply better art than most. Video games are an art form, an artistic medium; a video game is a work of art, the only thing up for debate is the quality. Some may be more artistically-minded (all art forms have some examples made with art in mind and some made for other reasons), but all are examples of the art form and thus are art. Though Shadow of the Colossus is no more "art" than Call of Duty, it definitely stands as one of the best games ever made from an artistic perspective.
I especially loved the ending; I love games that play with the role of the player by presenting scenes in which the interactivity is somehow dramatically limited or altered for emotional impact; other examples are the plot twist in Bioshock, the epilogue in Halo: Reach, and the final boss in Beyond Good and Evil.
As a note to others posting, art is more than visuals. As a general rule of art, it's not just paintings and pretty pictures, it's broader than that. It's about expression the human experience through the lens of human creativity. Storytelling, be it through literature, film, or video games, is art. Painting is art. Photography is art. One could argue, based on growing game theory principles, that the expression of human actions through gameplay is art. Point is, an artistic game is not an artwork simply because it looks pretty, it's an artwork because it presents a story, because it sets itself to a soundtrack, because it presents an experience to the player that came out of the imagination of a group of artists and designers. That is art.