Did you save the file as a jpg originally? jpg compression sometimes creates strange artifacts in relatively flat, darker areas of an image that are hard to get rid of. I usually save as psd or png for that reason, only using jpg when I absolutely must.
Try selecting the area and blurring it using a filter like surface blur.
Someone also mentioned Filter > Noise > Reduce noise, click "Remove JPG artifacts" and play around with the settings, but never tried that myself.
I'll ask around and let you know if I hear of any other options.
EDIT: It could also be an issue with bits/channel. If you are using 24bit color (8 bits/channel), that may be the best "gradient" available to you for your image. Usually 8 bits/channel works fine, but for some images you need to change to 16 bits/channel to get finer control over the gradients. (Image > Mode > 16 bits/channel). Note that there are some disadvantages to 16 bits/channel--some filters won't work, for example.