The problem with paletted textures is that to get the colour for a texel you first have to look up an index in the texture, and then look up this index in a colour table (=palette). This requires two reads for point sampling, and lots of more reads for filtered sampling. Additionally these reads can spread out over memory, defeating some of the caching schemes.
One of the original reasons to have them was to safe memory, but as memory becomes cheaper the pressure to use them is reduced, especially as texture compression schemes like S3TC (=DXT1-5) have a similar effect. That's why they're not supported on many modern cards.
You can do some effects with palettes, like for example changing the colour of an object by rendering it with different palettes, but you can do similar effects with a pixel shader nowadays.