Got to Tools > Batch Processing
Browse for the folder with the files you want to convert using the "Add Folder" button.
Select an output folder different from the input folder just in case.
From the "Format" drop down menu, select the output format you want (.gif, .jpg, etc.).
I would choose the same format as the original images.
Here is the key part; go to the "Transformations" tab and from the "Convert" tree, select "Convert to Colours".
Click "Add" and some options will show up on the right pane.
Select 256 to have as many color combinations as possible.
When everything is set up, click "Go".
Let me know if it worked.