To my complete lack of surprise, I find that I agree with both sides of this question.
On the one hand, yes, it is terribly annoying to see a film that is essentially intended for an adult audience while being inflicted with the noise of a horde of disappointed kids. On the other, I have firsthand evidence that "Fantasia" (and the recent follow-up, "Fantasia 2000") can be seen by children as small as three years old.
How do I know this? I know because my son has been watching the former (on video, granted) since he was three - it is one of his favourite movies - and the latter, ever since it was released on video. He's never had any trouble understanding it, and he's grown quite fond of classical music. In fact, he often refers to pieces as being "from Fantasia".
Now, of course, this doesn't demonstrate that the film can be seen, in a movie theater, by small children. Kids are notoriously incapable of sitting still in a darkened movie theater, and a film like "Fantasia", with so many slow passages, requires a lot of attention from them. Small kids often aren't capable of that attention.
On mature reflection, I'd say: Don't cheat your kids of the joy of watching the "Fantasia" movies. They're just fine for children. But, let them see the movies on the VCR at home - don't take them to see the films at the theater.
And, hey, isn't that "Firebird" sequence in "Fantasia 2000" amazing?