Hmm. Sounds suspiciously like the Baldur's Gate movie problem.
Warcraft 3 uses Divx for it's movies. If Baldur's Gate uses it as well, then it definately related.
Because War3 uses Divx (http://www.divx.com), it might be easy to debug because I think it's open source. I might as well try fixing it.
Another thing that's interesting to me, like nearly a year ago, I would guess, I and a couple other people were asking blizzard to release their trailers in a better format than quicktime. Most people in the forums would say quicktime was the best, and we would say, "have you ever heard of divx?" We suggested divx because of superior compression and quality. (And for me, it works in linux =) And a couple weeks later, they rerelease a bunch of trailers under divx, and announced they licensed it. Even on their website they list for the divx trailers "PC/Linux" which is a big deal for me =) And they like it so much they use it in their latest game. Maybe this is another reason I got the beta =)
(and another thing, open the first page of the game manual, it lists they use divx, Freetype 2.0, and zlib. No wonder it works so well under linux. Maybe one of these days they will use SDL ? =)
Jesse