It could be your file format. If you have different file formats open at the same time, they would obviously have different palettes. Switching to a 32-bit file format should get rid of the problem, seeing it doesn't actually use palettes at all anyway. Then, you can save it as something else later.
EDIT: ^^ What he said... ^^
EDIT: ^^ What he said... ^^