Well, chick has beaten me to most of the things I was going to point out. Here are my suggestions (sorry for repeating what she said):
--labels I: an outer glow would definitely help readability. I would recommend, rather than making the glow white, use the eye-dropper tool to select a colour very similar to the background parchment, and then make it brighter and less saturated. White could end up looking strange against an aged paper texture. Another thing you can do, instead of using an outer glow as Chick said, you could just create a layer below your text but above all of your other layers, and paint a blob under each label that hides what is below. This is more work, but if done with care and delicacy can look good (the advantage over outer glow is that it would look less regular and digital; for someone new to this, though, outer glow works fine).
--labels II: some of your labels are very blurry. For example, Goldenport and Wayfarer Belt are quite hard to interpret, and the label in that circular forest to the north is completely unreadable. This is due to blurriness of the text, overlapping features underneath, and the elaborate decoration of the font. If you can reduce the blur, you'll improve readability. Also, moving some labels may be worthwhile. For sites/settlements, there is a usual pattern of having straight labels (not on curved or angled paths), and trying to place them close to the settlement to the right or left. For example, if you moved the label for Newport to sit just above-left of the town icon, and so not overlapping with the islands and coast, it would look better.
------you can do the same with Goldport
------Fort Galen could be moved to the lower right of the site marker
------Blackport could be made into a straight label (not sitting at an angle), but is probably best kept in the bay where it can fit
------Gogota is better, but another convention is to favour the upper right, then upper left, then lower right, then lower left, then centre above, and finally centre below. Since you have the space, I think Gogota's label should move to the upper right.
------Megadrome, Rorak and Astrya (I can't even tell if that is the right name) could all be moved.
------etc.
--labels III: try to remain consistent with the font, and size of text. Thus, all settlements should generally have the same size text (you can make it a bit bigger for capitals, but not much); all mountains should have the same size font (sometimes people use a different font for mountains to settlements, but for now, I'd stick with the same font). Try to keep the text consistent in darkness, too: eg. the label Infis is clearly darker than the compass rose. Another common thing people do with labels is to make them a very dark brown, rather than completely black.
------Your mountain labels, I think, are too big.
------The label for Gogota is, I think, a good size for all settlements;
------Brownfields is a good size for all geographic features;
------your sea labels could probably be made smaller, but often they are allowed to be the largest label on a map (not including the title).
------you mentioned that you deliberately put Infis and the compass rose overlapping? I agree with chick: I think it would look better if the title sat below the compass rose.
------Oh, and--no offence--the font beneath your legend is just silly. It simply doesn't match the rest of the map, although I can see that you may have chosen it for legibility.
--colour: your map seems to make a very selective use of colour. The faint green glow around the northern forests/swamps, but absent in the south, and the comparatively bright yellow in the southern badlands, make those areas stick out too much, in my opinion. It might be intentional, in which case disregard what I have to say. My recommendation to you is to either a) add a (very) light green tone to the entire land area, or b) remove that colour and try to indicate those areas another way, or c) add a subtle colouring to other features, like mountains, hills, grasslands, farmlands etc. (a. and c. together is probably the best option, in my opinion). At the very least, however, I think you should make the colour consistent--the forests on the southern island should have the same treatment as the ones in the north.
--map elements: one notable feature of your map is the large amount of black and near-black that is on it. There are the rivers (which I'll talk about below) and there are the mountain/hill/forest brushes you've got. I think your map would look better if you dropped the opacity of each of those elements substantially. The forests, for example, which are probably now at 100% opacity: see how they look at 40%; mountains and hills: try 60%. You might need to go higher or lower than these values, but it can't hurt to see how they look, can it? Reducing the opacity will also mean that the settlement labels (which can remain dark) will show up more, and that is how it should be in a map.
--rivers: the solid black rivers look rather strange. I think there are two ways you can do these rivers: either make them so thin that they don't need to taper at all (i.e. the entire length of the river is no more than ~2-3 pixels wide), or make them 'hollow' (i.e. continuous with the sea, with a thin black outline). The first option will have the additional effect of making your map look like it is a much larger scale, which may be good or bad depending on your preferences.
--forests: I agree with chick about the circular forest in the north. As a solution, I would recommend simply adding individual trees elsewhere in the map. One of the good things about using that style of tree brush, is it can look good having just one or two trees sitting in a grassland area. Try adding single trees (or trees in clumps of 2-3) in other parts of the map, with a greater density near forest edges, and a lower density away from the forests. This should make it look as though your forests fade away, rather than coming to an abrupt halt. It is important not to overdo it, though, so keep zooming out and running a critical eye over how it looks.
--texture I: I was also going to mention the rectangles in the texture. Since you added them deliberately, perhaps you should just make them a little less obvious. Go around the rectangles and, every now and then, blur the edge so that the lighter parchment blends with the darker. Leave enough of those edges unblurred that you maintain the clear separation of one from the other. Try that and see how it looks.
------the scribbles in the top left look great. I really like them
------the coffee stain is probably too clear. Can you blur it a bit?
------like chick said, adding one or two other stains may be worthwhile (although comparatively small, I would suggest).
--texture II: also bear in mind, the effect you are going for with the rectangles is slightly ruined by the fact that it only effects the paper texture. If this map had indeed been sitting beneath a chest, and light had caused part of it to become bleached, than the text, lines, colours would also become bleached, not just the paper. I don't know how you did those rectangles; can I assume you applied them to your original parchment texture? The way I would do it is to create a saturation/brightness layer (I assume GIMP has such a thing) above ALL of your other layers, add a layer mask for the areas you don't want to appear bleached, and then play with the brightness and saturation levels and see how it looks.
--nitpick I: you have mispelled 'palace' in the legend
--nitpick II: your settlement icons look good in the legend, but are too small to easily discern in the map proper. For example it is quite difficult to tell that that icon between Gogota and Megadrome is a palace. Simplest solution is probably just to make the icons bigger on the map.
--nitpick III: the circular forest around the mountain in the north: it looks a bit strange that there are no trees 'behind' the mountain.
--coincidence: is it just a coincidence that you have a sea with the same name as the Australian town of Cootamundra?
That's all I can think of, for now. I hope it is helpful. Feel free to ignore any of my suggestions if you disagree with them. Also, post updates when you have them; this is a great website for getting feedback. (You might want to ask a Community Leader to move this thread into the WIP subforum, or start a new thread there)
THW