OK for my game, the textures are based on tables of 256 colors each, and so changing one color on the table would change all of that color on the texture... Any idea how to do this?

why would you wanna do that?

GL_EXT_shared_texture_palette might be your anwser... but remember that palette-type textures and modern GPUs don''t mix very well

You should never let your fears become the boundaries of your dreams.