From your description you are trying to make a gradient on a color-indexed image (a GIF, possibly). The gradient tool cannot work on such images, you have to convert them to RGB (Image>Mode>RGB).