The first thing that I believe could be adjusted is the borders between different areas (this applies to different areas within each zone). For example, Crystalsong Forest: there are three distinct areas in this zone and at the edge of each there is almost a straight line separating it from the next. You could try placing the tiles in a more jagged fashion to give it a more natural blend.
I also believe that some of the areas look quite empty (this could be to accommodate the size of large armies are such though, in which case that's fine). For one, Coldarra could use some sort of structure in the center to represent the Nexus. Grizzly Hills might look better with the tiles used in Howling Fjord. It looks rather dark at the moment. Some more trees might be nice too. If you're concerned with space, you could make a new doodad that uses the tree model, remove the pathing, and scale them down so that you can have a more realistic amount of them and space them out as you please (they won't have to be placed on the grid if you remove the pathing). Crystalsong Forest could use a few trees as well. Dragonblight and Storm Peaks don't have much except bones and the odd mountain here and there, but I suppose in World of Warcraft it isn't all that different. There is a forest in southern Dragonblight though. That could be added. You could always throw in some of your own creative touch as well.
Some ruins or small decorative structures to fill some more space, where trees just won't cut it, may prove to be a nice addition as well. This particularly applies to Zul'Drak, Icecrown, and Storm Peaks (Ulduar).
ANYWAYS, that's me being critical, so feel free to agree and disagree as you please. While writing the above, I didn't entirely consider the presence of controllable structures, so I imagine they could take up plenty of room and make half of the above pointless or even cause the map to be cluttered.