There are a few things to try/check.
1. Are all of the relevant layers on and have an appropriate plot style?

The above picture shows the layer properties that I needed in order for the colors to be plotted. The most important things are that the layers are on, thawed, and have a plot style ("Normal") which allows colors to be plotted.
The below pictures show how to find which layers you need to address. They live in a couple places since some of the layers are associated with the table and others with the surface.
- Surface Legend Table layer



2. Have you tried changing the layer of the table?
I can't explain why it works, but I have had luck with changing the layer that my table is on. I create the surface legend table which is automatically placed on a layer called "C-SURF-TABL" and then I select the object and change it to any other layer (I typically create a layer called something like "C-SURF-TABL-SurfaceName." For some reason, after I do this, the plotting works like it should even though all of the layer properties are identical.
3. Last resort, have you tried exploding the table?
Exploding is a bad habit that should be avoided. That said, it is great for understanding what is going on under the hood.
Exploding in this case lets you see the properties of the things that are giving you trouble. If you explode the surface legend table twice, you can click on those color palettes to see what layer they live on and what their properties are. These are good clues for how to solve your problems.

Additionally, once they're exploded you have more direct tools to control their appearance so you should be able to get it to appear exactly as you want. The big downside is of course that you lose the dynamic link to the surface so if the elevation analysis or the data are updated, you need to go back and edit the table. This maintenance also provides room for errors to enter your work if you aren't diligent with the upkeep.