I'm doing it as having a the same 4 colour palette throughout but the palette used is selectable by the player from a variety of presets. That's ok right? :)
As long as the palette selection tool is like...by keyword and not color, I think you're fine. If the palette selection has the whole availability of all the palettes it'd still be more than four colors, but like if you had a button for 'red', 'green' and 'purple' with the words written there it should be fine I think!