Too few Races, or too many races-I flip on this every so often. Sometimes I think it should have been another Orc Vs. Human, other times I think it should have followed the original plan and gone with a eight races game.
No Navy- Alright, I loved the Navy in WCII in the multi-player games with my friends I always was the one with the huge navy that crushed all others, and it sucked for me to see in the Beta that there was no Navy to play with anymore.

Too RPG- This was the big one. Heroes are a good Idea. Making them the centerpiece of your army, where without one you're royally screwed, and making it so you had to manage their spells, items, and keep them alive while dealing with your other spell casters was not.
Bad Animation- Actually it was good animation, just unrealistic. I personally prefered WCII animation above the new style in WCIII.
Any Thoughts?