Twice have I seen something like this; first time while figuring out how to get SW3DFX to work with an older version of GliDOS and the second time with vanilla sw.exe on XP, which I resolved by right-clicking sw.exe, going to Properties/Screen and changing "Usage" to Full-screen.
Obviously 2 completely different situations, but something's definitely corrupting the palette.
If SW's working ok under pure DOS (you didn't say but I'm assuming yes), then it's got to be a Windows thing, though changing your desktop's color depth as suggested above is quite unlikely to yield the desired results because the video hardware is being accessed in 2 completely different ways if you're indeed using the official drivers. Not that you shouldn't try, though.