I found myself looking in a dictionary for "art", just because I was curious as to the exact definition of it, and it was "The conscious production or arrangement of sounds, colors, forms, movements, or other elements in a manner that affects the sense of beauty".
So, if one were to follow this definition, I suppose AMV's would fall under art. We could just set random clips to music, and it would be the same as if someone just splashed a can of paint on a canvas. Or, we could place each and every clip perfectly, much like a painter places his brush strokes. More effort goes into the latter, it is generally more appreciated by most people and is what they will consider art.
But then again, some people might like the random splashes of color (the balloon-popping method comes to mind, where a person tacks balloons of paint to a canvas and throws darts at them) just as some might like random clips set to music.

