That mountain texture is heavily pixellated but despite it, I think its much much better as a map than it was originally. Maybe we can help that resample and get the pixellated effect down a bit and then you have a great map going on.

I am not sure what happened between the old and new but if you have the ability to separate the mountains off then I think that you first must make sure that your working in true color, or 16 million colors, or 24 bit, or 32 bit color - they are all much the same thing. If you have a palleted image then it would cause issues and your paint app would probably either not let you do a nice resample or would choose a useless mode for you without saying. So try to up the color depth to full.

Use bicubic resample if you have the option or bilinear if not. If your really stuck then resize the mountains to double or quadruple the size you need which will be really badly pixellated. Then blur it a lot so that it fixes it and then resize the image back down again to normal size. Once you have an image at higher res than you need looking ok then its rare or hard to botch it from that point. Resampling up is always harder than down sizing.

What did you do to it to change the res ? I don't even know at this point which app your using.

I really should write a comprehensive tut about resampling as theres always a lot of talk about it and a lot of confusion. There are many gotchas and some neat tricks to explain too.