Try running transpal.exe on the palette. Transpal is probably in the wad2art folder on the duke cd.
From my palette change doc at rtcm (which needs revising again, sigh):
<BLOCKQUOTE><font size="1" face="Verdana, Arial">quote:</font><HR>
3. Fixing the palette.dat file
The palette.dat file contains more than just the palette. It also contains the number of shade tables, the shade table information, and transparency information. This information isn't set up automatically when you change the palette, nor does it use the old information by default. There's a program called transpal.exe that can fix the file, assuming you know what the figures to input and the right keys to press are.
The command line parameters for transpal are:
Transpal [number of shade tables] [translucency number] [r] [g] [b] (rgb values are optional)
There are usually 32 shade tables in the palette.dat file. Originally, there were going to be 64, but the number was dropped to 32 for the sake of slower machines. I don’t recommend using any number but 32, as some odd bugs have crept up in my tests. Also, you would be forced to re-shade any map you have already started with the original 32-shade-table palette.
The translucency number ranges from 0-256. Were it set on 0, the first translucency setting would be totally invisible, and the second would be solid. If it is set to 256, the first translucency setting would be solid, and the second would be invisible. 160 and 170 are the example values, which appear similar to the standard values.
The RGB values are optional. I don’t recommend using them. The default values look fine. Feel free to experiment though.
Once you’ve typed the correct command line information, hit enter. You’ll see colors streak across the screen. There are three key commands for transpal that you can now use.
Esc: exit without saving
Enter: save shade tables and translucency tables
Space: save ONLY the translucency tables.
You’ll probably want to just hit enter and save both.
According to Silverman, some teams wanted to use another program to write the shade table information, hence the reason for the space command. The reason for this is likely to create full-bright colors. You may have noticed full-bright colors in the default palette. The last 16 colors are not affected by shading in any way. This is because the shade tables were modified to prevent this. You can modify the shade tables to add full-bright colors to your palette using OpenGL BuildTouch 2.1. I must warn you that it is a very tedious process due to the number of shade tables.
<HR></BLOCKQUOTE>
Let me warn you that transpal isn't perfect by any means, and it gave me a crapload of hand editing to do on my most recent palette (mine was a very radical change though, so I'm not too surprised. Should work more or less fine on a palette that you just added a few colors to in the fullbrights. Check with oglbt2 to make sure afterwards though, and make a backup before running transpal.)
Hope that helps.
full doc: http://dukertcm.totalconversions.com/Knowledge_Base/Document_Palette-Changing.shtml
RTCM main: http://dukertcm.totalconversions.com