Hi Sunergy, welcome to the Guild. That's a pretty decent map; the colors don't really do it for me, but that's just a personal preference.

As to your Help Wanted points:
1) roads - they look fine to me. (Could be I'm biased though, since that's the same way I do mine. )
2) territory borders - I'm not a huge fan of the super-bright colors. The actual borders look fine though, no pixellation or ugliness that I can see.
3) paper texture - yeah, it's a bit much. Maybe just lower the opacity and see how it looks at different levels? I'm not sure what program you used to put this together, but if it's PS or Gimp, you might try copying the paper layer and reversing it right to left on top of the original and see how it turns out. I've done that with similar textures and it can sometimes give an interesting look.
4) ocean color - not a fan of the two-tone look. I'd like it much better if it was one color all the way through.

All of this would be made easier if there were a bit bigger version to look at...