I like the general feel and look, its very nice I supose the color zones are diferent countries or empires, but maybe it's a bit saturated, at least for my tastes. Most of the map is has a color quite plain and the color zones are very highlighted. Maybe it's just a matter of adding a coulple more of countries to fill all the land portions.

The mountains and hills are very clean.

And for the labels... I like them. It's just there are so many of them! That's why I think they "dominate" the map. Try make them a little shorter or put less of them and I think it will be an imprivement.