Update on my personal situ:
(Vista 64 still)
Installed the High Res pack, renamed ddraw.ini, now I have to manually lower my res to match my preferred for the game (960x600) or I get the color problem in Fallout 1 as well. Compatibilty is set to Win98, 256 color, and disable visual themes.
This method also works for Fallout 2 and is still quite inconvenient which is why I haven't closed this question.
I'm pretty wary of adding too many mods to the game. Really I'm only interested in fixing the aspect ratio on my monitor with the high res patch and possibly fixing the missing children "bug" in Fallout 1.

This combination solved my Fallout 1 issue (in this order):
F1ChildPatch
rename/remove ddraw.ini
Fallout1 High Resolution Patch 1.1
Compat Win98, 256 color, disable visual themes

For Fallout 2 using killap's patch + high res mod and enabling dx9 (mode 4 under graphics) solved my color problem. I'm now having trouble with the FMVs though, but that's a seperate issue so I'm going to say this problem is now solved for me.

If I have both the high resolution patch and killap's unofficial patch, what order should I apply them in to make it work? Busy downloading the game now, but want to get it right first time if possible :)
Running Vista 32, C2D@3GHz, 8800GTX, 3GB RAM

You should install killap's patch before the high res patch.

I changed [system] art_cache_size from 8 to 4 in the CFG file. It seems to have solved the issue. However sometimes the game boots up with the incorrect colors. If I exit and start it again it usually starts the 2nd time with no problems.

yes, I downloaded killapps patch and changed the garphic mode in the ddraw.ini file from 0 to 4 and it fixed the inverted colors. Now the videos are kind of screwed up but that doesn't really bother me.

I installed Killap's patch, and changed the mode to 4. Now everything works great (well, except for the movies, as Synergy said, but if I want to see any of them, I can just look on Youtube. :P) Thanks for helping me to enjoy this magnificent game in its full intended glory!

Just changing the art_cache_size to 4 solved it here. Thanks for the fix, This should be written in an article (with a clear solution rather than a forum thread link) or pinned down.

For people still having problems under Vista, I found that some of the issues were due to the application needing to have administrator privileges (someone mentioned this to create the cfg file but it also affects the colors for some reason). A word of caution - if you apply the unofficial patch it appears to check if the code is running in compatability mode (it may do this without the patch - but I applied the patch first and it doesnt do it in fallout 1 with no patch).
Anyway I simply right click the icon and say run as administrator and that appears to help with the colors for fallout 1 and fallout 2 (as well as castles 1 and 2).

I found the easiest way to address this is to:
right click on the icon
choose properties
click on the compatibility tab
check the box "Run in 640X40" screen resolution
Click apply
Happy gaming!

I had this same problem on a an IBM t42 until I installed the ATI drivers from their site: http://www-307.ibm.com/pc/support/site.wss/MIGR-41918.html.
To the person who had the issue with their thinkpad earlier in the thread. Flip your laptop over and there should be a sticker with your model number on it. Mine is T42 2378 FTU, for example. If you google that with component controller, it should take you to a website similar to the one I posted with the video driver you will need for your particular laptop.
I'd also grab the thinkvantage autoupdater while you're there.

In Vista 32, I right clicked on the icon, set compatibility mode to Windows XP SP2 and ran as administrator. That fixed it. This is the easiest way to adjust it without editing files that may come back to haunt you if you did not get it exactly right.

I also have the shifting colours problem. I'm trying to run fallout one and two on a machine with vista 32, dx10 and a wide-screen monitor, which I can also set to 640x860.
I've tried setting compatibility mode. I've tried execute as admin. I've tried changing art_cache [system] to four. I've tried endless combinations.
However, it still manages to flip out on me every time I start it. after merely seconds, my screen explodes with pinks greens and yellows that aren't supposed to be there. Can anyone help me?

Just thought I would add my 2 cents. For some reason in Vista 32, when I run Fallout 2(with Killap installed) with no Windows Explorer windows open then I sometimes get weird colors. However, if I run it with at least one Windows Explorer window open (My Computer for example) then it will always run with no weird colors. Just try running it with a least one Windows Explorer window open and see what happens. I just made a .bat file that opens one for me when I click it and it has worked every time. Below is the contents of my batch file:
explorer.exe
cd/
cd Program Files
cd GOG.com
cd Fallout 2
Fallout2.exe
copy this into a plain text file and save it as a .bat file then you can make a shortcut to it on your desktop.
This also allows you to play without the movies being messed up, unlike changing to mode 4 for Killap's patch. Just keep it on mode 0 and use the method I described above.
*UPDATE*
If you use Vista or Windows 7 Beta and sfall AND the high resolution patch, LEAVE the line as "mode = 0" in the the ddraw.ini file and CHANGE the line "COLOUR_BITS = 8" to "COLOUR_BITS = 16" in the f2_res.ini file. This will fix ALL the funky color problems and keep the movies from being messed up!