If you want to try your hand at something a bit more robust you could download and install GIMP. It is very full featured like PhotoShop, but several people on this board use it and there are already several tutorials up for mapping with it. Oh, and best of all it is FREE! Obviously the learning curve would be somewhat steep considering your experience, but if you are willing to try to learn I think it would be a great direction for you to go in.

You can then import the existing map on its own layer and then draw right over the top of it as you see fit without changing the underlying map.

Do you think that might be something that would work for you?