GGN talked me through a easy way of re-ordering palettes using Deluxe Paint.

Right click on the icon to the LEFT of the icon that looks like an S (or a $).  A window will open below the toolbar.  This new window has a copy of the palette in it.

Then, left click on the colour in this small palette that you want to move.  Then click on the 'remap' button.  Click the colour in the palette that you want to swap the previous colour with.  DONE - you've moved a colour in the palette and your image will be unaffected!

Repeat and rinse until you have the colours in the right order (IIRC, black 0, white 15, e a o at 4...or whatever the rules stated).

Hope this helps a bit :)