The skin editing in QMe is probably the most polished part of the program. You can even undo edits that you make while drawing on the skin using ctrl-z! (*)
http://www.btinternet.com/~chapterhonour/qme-pal.png highlights the button (top right) and shows off the dialog. You can remap colours one by one if you double-click them, then pick the replacement colour from the pop-up. It's pretty laborious to do that though.
The quicker way to replace colours all at once is to untick the boxes to the left of the row. This replaces all the colours in that row with the closest match in
the remaining checked rows. That last bit is important - if you have lots of fullbright oranges and reds you want to remove from your skin, make sure that all the non-fullbright orange and red rows are ticked first. Otherwise you will get poor results!
(*) 3d view only