I use paint shop pro 7, im pretty sure u can download a trial for free, and if you open the picture, with the default interface, on the right it shows the palette. usually you'll just see a palette with colors going smoothly into eachother. you don't want this, it means it has a 16 million color palette.
to make it 256 colors you need to load a palette that has that ammount of colors, but ofcourse, you want the colors in the picture to match the ones on your palette, otherwise the color would pick the closest matching color, wich may be for example, if it has green, and you don't have it in your palette, it'll become blue (if this is in your palette)
I'm quite positive there is a detailed palette making tutorial in the tutorial forum. If not, download utahjazz's tutorial and skip to the part about palettes.