[2010-08-12: It seems that perfect solution is found. Start reading article from bottom. :)]
This is usually restricted to menus. Once game starts, everything looks fine (ok, water has artefacts too), but from time to time, whole game gets garbled. There is nothing to do other than exiting game.
I tried various settings on compatibility mode without real success. Setting compatibility mode to Windows XP (where game looks good) made things even worse since Starcraft started reporting that it cannot load a file (font\font.gid). Neither combination of settings got palette problem solved.
Unrelated googling threw me a solution. Just open Screen Resolution window and run Starcraft (with that window still open). Colors are as they should be.
I haven't tested this on Vista yet, but if you have a same problem, it is worth a shot.
Why exactly this works - I have no idea.
[2009-03-06: Notice that you still need some compatibility settings. Here are ones that work for me in Windows 7. Disabling display scaling enables me to have higher DPI (120%) and still use my map (otherwise, place I select on map isn't place where I end up). Without disabling desktop composition, I cannot even switch to game and without administrative rights you may stumble upon some problems if you are running from Program Files folder (write forbidden for normal users). Checking other stuff didn't make anything better, so I left it off.]
[2009-06-09: With Windows 7 RC, things got worse. Even with every checkbox selected, Windows 95 compatibility mode and resolution screen open, I cannot reproduce proper screen every time. Sometimes it works properly, sometimes you can get it to work by pressing Alt+Tab repeatedly, and sometimes it is best to exit and enter again.]
[2009-08-28: This workaround works for final version of Windows 7. It does not work every time but success ratio is well over 50%.]
[2010-08-12: One annonymous commenter suggested solution that includes registry changes. All I can say is that it really works. I did test it only on Windows 7 (64-bit version) and it works perfectly. I do hope that it works on other versions (Vista also). I took liberty of packing those two hacks into one zip file. Do leave comment if you find it working (or not) on other versions.]
[2017-04-19: With patch 1.18, issue is finally resolved.