I have solved a problem (with the help on Alastair at the end of Skype at the weekend).
The Colour Table was not showing in Photoshop at the point where you finish working with the image and are at Save for Web and Devices. The Colour Table was greyed out. I have sorted the problem.
On the screen (upper right corner as seen in the screen shot* above which is what you see when you are in Save for Web and Devices) you have to make sure the field at the top which sits under Preset, has GIF in it. Now I do not know what I had before; I do not know if other options work. All I know is that the Colour Table has returned and furthermore it is still there (as GIF) when I repeat the procedure. QED.
* When I figure out to get a closer image of this I will post it.