You aren't doing anything wrong- it's just a limitation in the firmware. Most of
the images in the iriver firmware use a 256 colour palette, and some of those pallettes are shared among several images like the error message mentions.
So say for example you have the edited image, when you save it photoshop most likely changes the palette so only the necessary colours are included. But then that throws off the other images in the firmware which usually share that palette.
An example 256 colour palette...
But if your image is made up of pinks, oranges and greens, the program might save it with a palette like this...
The only real way of sorting it out is to make sure all the mentioned images share identical palettes.
Hope that helps.