Ah, this age old problem. Here's an old post of mine explaining how to convert a PNG:
QUOTE (shinyjiggly @ Feb 3 2011, 05:21 PM)

Well, I usually use the GIMP to change my color depth (it's free!) and it works pretty well as long as you have more than 16 colors total (otherwise it automatically converts into a 16 color instead of a 256 color). But your problem seems to be an amount of colors over 256.
If you can download and use GIMP, you can use a tool called "colorcube analysis" that will tell you how many colors you have in your picture. If it says that you have more than 256, you might want to use "posterize" at the lowest possible setting where everything still looks nice.
Once that's over with, you can convert it to indexed mode. Just remember that unless you want dots all over your picture, don't use the floyd-steinberg method (which is selected by default...) Once that's done, you can save it and use it!
One thing I would add to this is to not use posterize because it turns out that the index option picks out better colors than the posterizer (the posterizer tends to pick colors out a set palette of a chosen scope and the indexer actually goes with the most used colors in the image).
But, most spritesheets will not need to worry about the color limit.