Great map - very evocative! Your design choices with the various elements keep things simple, but fit together beautifully to create that old-world style. Like the others, I particularly like the forests - they have enough detail to be representative, but still keep the color palette small, which is key to the overall effect. Being rather a newb with PS/Gimp, could someone briefly describe how to get the outline effect seen on the forests? It looks too precise to be a lighting effect to me. I would also have to agree with Jezelf about the mountains - they seem too similar to the hills to me. Perhaps a few hand-drawn strokes in gray across each one would differentiate them without being overwhelming? As for the fonts, I think they're fine. They don't seem at all out of place to my eye. I notice, however, that the regional labels ("Kingdom of Grenwick" for example) are underneath your forest layer. That seems strange to me, but perhaps it was intentional.
Again, fantastic map. I'll be saving a copy in my reference folder of inspirational examples.