My first thought was to use Europa Universalis 3. (and not only because I was playing it today) The map is simple, yet still has some medieval-esque detail to it, is already divided into regions, and most modding in the game is done by editing simple text files and letting the engine churn out the results. If you wanted to use different sprites or textures it should just be a matter of changing what file is loaded.
Of course, I haven't talked to anyone who wanted to build their own map from scratch with it, so it could be more difficult than I think.
