To get the palette right when converting images for Wind-Ups I use a program called ThumbsPlus (evaluation version available at www.cerious.com)
NOTE: I am using ver. 4.50 of ThumbsPlus so some details may vary with the newer releases.
First you need to open one of the .gif images located in the IMGS folder within the WIND-UPS folder. I used BG02.GIF as it has the most colours, the other .gifs may be fine to use too. When you have opened the BG02.GIF file in ThumbsPlus go to the file menu and choose "Save Palette As..." then simply save the .PAL file somewhere.
Now open the image/icon you want to use in Wind-Ups (320x240 for backgrounds, 24x24 for icons)
With the image loaded select the "Depth" option from the "Image" menu.
You should now have a dialog box open with various colour depth options.
Select 256 Colors and from the "Palette" drop down selector list choose "Load from file". When you are prompted for a palette file locate and select the .PAL file you saved earlier. For "Dither" I use the "Floyd-Steinberg" option.
Click "OK" and you should now have a 256 colour image with the correct palette for Wind-Ups.
I hope this was of use.