Wow, beautiful style! I love the colours you're using. If you hadn't said you were open for critique I'd feel overly nit-picky for these points, but:
- I think the labels seem out of place because they don't look like they're painted at all, and as such they don't combine with the map very well. The dark outline with white font helps the text stand out, but I don't think it would be painted that way. The opacity in some also helps clarify size of towns, but same issue here. Since this map doesn't seem to be made for precise navigation anyway I think you could get away with labels which are less clear, but fit the style of the map better.
- I'm not sure what's going on with the grey area near Narak. Are they cliffs, stone mountains?