Wow it looks nice. Please keep working on it. How "large" did you have in mind (land province, water provinces)? I have a little talk-paper on maps which might have some things to consider though its more about random-generated maps.
http://www.dom2minions.com/maps.shtml
Im not sure how large the provinces were going to be but your terrain areas might be large enough that a nation might end up surrounded by only one terrain type. Something to keep in mind (ctis cant take anything but mountains, ulm surrounded by all the good farmlands, etc)
I know more gimp than photoshop so this next part might need some translating. In general terms.... make a copy of the map, lower the colors gradually to something like 16 colors you should get a cartoon image of your map with big areas of brown, blue, green, white. Select a color like red. Then use an "edging" option (might be named something like borders?) which shouild draw red borders around all of the large color areas. Now go in with a line command and draw some lines chopping areas that seem too large into smaller portions. Remove everything but the red (drop paint, or "mask", or select-color and copy-to?). Bring up the original (well for safety, anothe copy of the original) and paste the red lines on top of it.
Usually this isnt perfect but its often enough of a start to change it form a massive job to a tweaking/editing one.
[ May 27, 2004, 15:07: Message edited by: Gandalf Parker ]