When you applied your palette to the files all 256 colors overlapped the originals.

Top palette box being original colors and bottom, your custom palette.


As you can see most of the colors from the original files are now overlapped by pink.
Which in most cases turns out like so.


What your going to have to do is sort out the original colors into a custom palette (Make sure these colors go in the same area as your personal palette ones and that there are only one of each color) and batch apply it back to the files.
(Backup all the files just in case things turn wrong when sorting and applying)


I find myself using PSP for this kind of job but the Optimize option in FF works just as well.
(Careful; darker colors tend to merge using Optimize)

Once you've got your files all batched and ready to go, add them back into FF, align, and apply your personal palette.
The PCX/PNG colors if sorted correctly will give you your desired palette.


Hope that helped.
BTW, your avatar quote: Haku-Men?

Edit: If anyone asks... I took these pictures off random sights; credit.