Very nice indeed, I like it a lot. Just to throw in some ideas: if you want to make it a maritime type map you may want to detail the costs but leave the inland areas 'uncoloured'. The oceans have a repeating texture you may want to get rid of (as does the land). I really like the clip art, but I think it might look better with more of it and smaller. Some labels on the journey paths (e.g. 'Here Sinbad slew the Gorgon') maybe? Most of all I'd really go to town on making a beautiful sea texture. I'm not a CC3 user but you could do it in PSP easy. It's hard to say, depends on whether you want it to look handdrawn or sattelite. If handdrawn (which would definitely suit this type of map) you might want to lose the textures altogether and use lots of labels and handdrawn effects...

... looking forward to see where you take this.