all the war3 videos are created using DivX so you definitely need an MPEG4 codec installed to play them.
Verify you can play the videos fine by downloading GSpot here:
http://gspot.headbands.com/
1) download and run the program. Now go to your Warcraft III/Movies folder. Drag and drop the first file "HumanEd.mpq" (the human cinematic) into the Gspot window. Let GSpot tell you if you have the codecs installed to play the file.
2) if it reports problems, please download ffdshow here:
http://sourceforge.net/projects/ffdshow
install this. Now try running the HumanEd.mpq file through GSpot again.
HUGE TIP: NEVER INSTALL NIMOS CODEC PACK IT WILL SCREW YOUR SYSTEM EVERY WAY IT CAN