an alternative that a friend showed me (that i didn't realize in five years of spriting/recoloring sprites) is that, in Paint, you can set a color to the back and front (that much I knew) and that the back color will become transparent when you drag a selection with the color in it (i also knew this), but I didn't really think about this, even though it was obvious.
If you make two palette examples that match the colors from light to dark, you can make large boxes that are the new color, and have the old current color as the background. Then, drag the image into the large box, and all the old color will be replaced with the new color in one simple step! (rather than searching out each color individually, like I used to do...)
although, this is either: A. obvious, or B. not helpful because you are not using Paint and/or don't have it (like me!)