The newest version of the High Resolution Patch/Hack/Mod fixes these issues entirely, provided you run it at 16bit or above (although it's mostly fixed at even 8bit).

There's several utilities out there for fixing it, as I believe have been linked above. Below i've created more direct links to them and instructions. So your process is this in general:

1. Install and set up the newest High Res for Fallout 1 from http://www.nma-fallout.com/forum/dload.php?action=file&file_id=1344
2. Obviously make sure you don't have anything running in the background that would cause issues - programs that'll come up with popups, etc.
3. Test to see if #1 fixed your issues.
4. If not, download and try each of these tools (one at a time) to fix the issue (they need to be run each time you play Fallout):
http://static.macuyiko.com/files/palettestealersuspender/PalettestealerSuspender.zip or the old version at http://static.macuyiko.com/files/palettestealersuspender/PalettestealerSuspender_old.zip if you don't like that one.
And,
http://static.macuyiko.com/files/w7ddpatcher/w7ddpatcher.zip
5. If none of those work (which I HIGHLY doubt) then try, as others have said, one of the many options listed at http://blog.macuyiko.com/2009/07/solving-color-problem-red-grass-purple.html
6. Have fun and enjoy this awesome game :)


P.S. for those getting the flickering / black screen, use this tool. It works great!
- http://www.labo-asso.com/download/fo1_screen_refresh.zip (Fallout 1)
- http://www.labo-asso.com/download/fo2_screen_refresh.zip (Fallout 2)

Another option is to do download my mod, (Fallout 1 only, for Fallout 2 use the Megamod or Killap's Unofficial Patch) because it includes High Res and the Screen Refresh tool. Hey I gotta put in the plug for my stuff ;)
- "Fallout FIXT": http://www.nma-fallout.com/forum/viewtopic.php?t=57362
Cheers,
--Sduibek

I found a fix that works for ALL games that suffer this issue on Windows Vista & Seven.

The problem is due to pre-DX8 drivers not loading correctly under the newer OSes (only happens on certain graphics cards).

Windows actually has a built-in fix, but no means to access it - clever. Google 'Directdraw Compatibility Tool 1.1' and use the provided app - it creates a registry entry for specified games to tell windows to use this special compatibility setting.

This method is 100% effective and doesn't compromise the stability of your system in the way that killing background apps does. Since discovering this I've not had to resort to any bizarre methods to get games working, and it's worked in every case I've tried.

Hope this helps some people out :)