There is a bug in Notes where it sometimes doesn't save the palette. The guaranteed way to force Notes to keep the palette is to import an image in PCX or TIFF formats.