It's no problem, you just have to find colors that compliment eachother for it to work. Even if its just a joke recolor you could say, match all the purples or even (since it looks like what you attempted kinda sorta) just inverse the image to its negative (It would make for an interesting look for a dark world setting).
Now If your looking for efficiency, try using photoshop then just use the paint bucket with its settings of 1 for Tolerance and the AA, Contiguous, and All Layers all unchecked and it will paint everything that has the same color as you clicked on.
Even if this recolor was just a product of boredom I might as well offer some pointers for future endeavours since you said you're not very good. I may not be a good spriter myself but I can offer help where possible.
