As James Henstridge notes, your PNG image is probably in indexed color mode. An indexed color image uses a specific limited color palette, and when editing such an image, GIMP will only use the colors available in the palette, mapping any other colors to the closest one in the palette.
In general, as James suggests, you'll need to convert the image to RGB color mode in order to freely edit it. However, if you just want to replace a particular color with another one, everywhere it occurs in the image, then there's another option: you can edit the color palette itself by using the Colormap dialog.
Just open the dialog (Windows → Dockable Dialogs → Colormap), double-click on the color you want to replace, and choose the new color you want in the color picker window that opens up.
The Colormap dialog also allows you to add new colors to the color palette, so that you can then draw using those new colors in the image (by first setting the color you want as the foreground color, and then clicking the button in the Colormap dialog). This can be useful if you e.g. want to replace only some pixels of a particular color with the new color. However, note that indexed color mode (in GIMP, and also in the PNG format itself) only supports a maximum of 256 colormap entries. If you need more colors than that, you'll have to convert the image to RGB mode anyway.