Make sure you are using a recent Wine version (e.g. 1.1.29 or 1.1.30) on older versions make sure that RenderTargetLockMode is set to readtex in the registry (see http://wiki.winehq.org/UsefulRegistryKeys). Hopefully 8-bit works then else I can't easily say what's wrong. I fear that your drivers don't support GL_EXT_paletted_texture well.
