I use PSP, but I opened Photoshop 6. I'm assuming this is will work for any version.
---
Open up a Windups bg, for example BG01.GIF in gpmm\wind-ups\IMGS.
Goto Image > Mode > Color Table.
Click Save...
Goto somewhere like your desktop, pick a name. Click OK.
Find your new image. If it's currently 8-bit (256 colours), do Image > Mode > RGB.
Now do Image > Mode > Indexed Color...
In the 'Forced' box, choose 'Custom'. The box will pop-up, choose Load... and pick your palette from earlier.
'Palette' should change to 'Local (Selective)'. Click OK.
Save the image as GIF, resizing if you need to (Image > Image size... click off 'Constrain Proportions' and choose 320, 240 as the size for BG, or 24x24 for an icon.
Hope that helps.
---
In Paint Shop Pro:
Colors > Load Palette... , Save Palette... and Image > Resize do the same thing.
-- Rico