I experienced a permanent palette-shift with OpenXCom during the last months. Switching to window mode helped; and with the newest AMD Catalyst Beta-Drivers the problem is now fixed.
Explanation: It all started with Windows7, which messed up the palette of old Direct2D-Games like Starcraft or MoO2 (but also OpenXCom) on some systems. That was fixed last year with a (optional) D2D-Patch. But this years things got messed up again. MS released together with IE10 a new version of this patch (that may caused graphical errors in Firefox), and AMD released a new Catalyst-driver, which seemed to undo the Win-Patch. Now they have finally fixed this again (offical note is only about Starcraft being fixed, but all the other D2D-Game are now fine too).
So if you experience a palette shift in OpenXCom, try to...
- check if the Windows 7 optional Direct2D-Patch is installed
- if you use a Radeon (5000 or higher) Card, install the Catalyst beta driver v13.11
or simply switch to window mode
- and if none of this helps, spam this forum with angry messages until it is fixed
Like I said earlier, if you can, use one of the OpenGL modes. Since you're running Windows 7 I'm pretty sure your card can support it. That makes the game run as a 32-bit surface.
Otherwise, OpenXcom doesn't use Direct2D. It uses SDL for its software rendering, in 8-bit. Windows 7 doesn't handle 8-bit video well at all (explorer.exe overrides the game palette with its own, so if you kill that, it doesn't happen. Even then, some colors still aren't right in OpenXcom.), so you don't want to use the SDL modes with it.
I don't know what to say if you're running XP though. The only game I've had palette issues with on it was Command & Conquer 95, and I think the only fix for it was getting different drivers.
CoolKid, does it look okay in windowed mode? If it does, you can turn on Borderless in the options.ini with your monitor's resolution to get it 'fullscreen' if you want.