Maybe using Paint is your problem. As far as I know it doesn't index the colors at all.
You should use Graphics Gale (my personal favorite, I use the free version and the only restriction is you can't export GIF and CUR), ASEprite also works, or so I remember.
Those programs also have other cool tools, like onion skin, layers, palette editor, etc.
EDIT: you can export your image to Graphics Gale, adjust color depth (which put the color used in the palette), set the colors in the desired order and copy/paste everything.