Click the options menu in the Color pallet, which is the down arrow with the 4-5 lines next to it, and change the color mode from Grayscale to RGB.
It just doesn't work
It looks like you using the pull down menu on the Color panel itself. The tipoff is the word sliders.
You need to change the color mode using the Image menu > Mode > RGB for new unsaved files.
The GIF format uses the Indexed color mode which limits it to only 256 colors.
This is mainly only used for web use with large areas of the same color. Its other use is for making animated GIFs.
RGB on the other hand can display over 16 million possible colors.
Of course, the average human eye will not be able to distinguish the differences between all these colors.
Bo is right. Your document is set to Grayscale. Until you set it to at least RGB, you won't be able to change your color pallet mode.