I think the reason the border seems out of place is because it gives the impression that the map is supposed to be on some sort of parchment; yet the texture doesn't affect the rest of the image. I would suggest either a simple black border as Lukc mentioned or incorporating the parchment/paper texture into the rest of the image so the two don't clash so strongly.

Save for the border I'm really enjoying this map. Nice and clean, easily readable and very effective color choices.