I don't have the game, and am as such not able to help, but I can say that the first thing anybody who can help will want to know is "What is your OS", so you might as well pony up that bit of information now ;-)

http://pcgamingwiki.com/wiki/Rainbow_color_problems_in_older_games

This, maybe?

I have the game, i'll give it an install and see how it goes for me. I'll be back.

Update: Working fine without the issue you mention and without even using any compatibility settings, but i'm using 32 bit Vista. The only issue is that when i exit the game it hangs and i need to shut it down directly using Task Manager. I'm guessing you're using a newer 64 bit OS and the problem will be caused by a newer 64 bit version of explorer, so i can't help with that. It's looks like a good game though, so i'd say make the effort to get it going.

I'm using Windows 7. I'm going to try DxWnd and see if that works

Something similar happens when I run original road rash. So I had to download it from other abandonware website.

Wow, you got something working on Vista, you may want to contact Guiness Book of Records.

I think I have the original CD somewhere but I'm a bit too busy right now to check which trick may work..
I'd suggest d3d wrapper
DXGL
WineD3D for Windows
DxWnd

All jokes about Vista aside, the reason i still use it is because it is the OS that has the best combination of BOTH backward and forward compatibility- which is what i want. If only backwards compatibility is needed then XP, but Vista has better support for newer tech (and for now is still supported) and the 32 bit version will always tend to have less issues playing older stuff than anything 64bit.

Obviously i don't use my PC for ultra new action games that need more than 4G of RAM though. If i did then i would not be using Vista.

Try killing explorer process first, like written in the link InfraSuperman gave, it solved most cases of rainbowcolors in games for me (C&C, X-Wing 1998, Diablo 1+2).

Just use VirtualBox and Windows 95/98/XP image? It helped me with HoMM 1 on win 8, and some other games that just crashed on newer systems.
Using trial image of win XP with VB is absolutely legal + u can rearm the license 3 times, that gives almost half od year of free XP system. Google it for more info.

Yes, joking aside, I am still surprised to hear that. Given that i have need for complete compatibility I keep on dual boot most versions of Win up to 7 (which I currently don't have a working copy) on one machine, however this pointedly excludes Vista which wasn't compatible with itself in most cases. I also have a win 8.1 machine as the "current" one due to not having a working win 7 code, but that will change soon. My suggestion, get a dual boot and use XP.

Well, killing explorer does fix the color problem, but my guys can't move, all of their movement options are grayed out :/

Nevermind apparently it takes 3 turns to remove a parachute