The .pal file format is from Paint shop pro. Are you tried the .pal files included in the tool? Maybe you can open with a text editor the ones saved with the tool and compare with the ones with photoshop to see the difference.
Maybe phosothop have some options to save the colors in .pal file that mess the structure?