OK... I'll break this down as best I can. Natty hit the nail on the head when he described layers. Everything you do, borders, colors, rivers, ect are going to be in different layers.
The first thing to do is fix those rough borders.
Create a new layer and label it borders.
Zoom in to about %600.
Select the brush tool, black color and size 3 px.
Systematically trace over the borders. It doesn't have to be exact but close will do. You will ultimately be deleting your original image, so don't worry about it.
Once you've done that create a new layer and label it rivers.
Do the exact same as the above with a bluish color of your choice.
Trace over the rivers.
One of the big problems with this map, imo, is that the tri-colors of the empires contrast with each other too much. Make the Ottoman Empire various shades of red, make the Austrian's various shades of white, make Hungary shades of Green. (or colors of your choice). That way the regions have some sort of graphical unity.
Next, you're going to want to apply these colors...
Create a new Layer and label it Ottoman Hungary.
Get your brush tool and change the color to something like burgundy.
Increase the size of the brush to about 20.
Color in the regions that comprise Ottoman Hungary.
Shrink the brush to maybe a 5 px and get in the little nooks and crannies of the border.
When you're done you should have a much clearer map of Ottoman Hungary.
Repeat the above step for all your regions, including the sea. When you're done, you'll have a better looking map.
Since I've got a mac I can't get myself Paint.net... but since Natty does perhaps he can point out how to make a new layer and what the brush looks like, how to change size and color, ect.
Once you've done this, post it and we'll go from there.