I had given up until I tried to run another old game that appeared to have the same problem, Worms Armageddon. Again the same messed up colours. But apparently there is one sure way of preventing the whole situation in Worms & Starcraft:
Kill Explorer and then run Starcraft from the task manager.
i.e. ctrl+alt+delete -> Task manager -> Processes
& end process "explorer.exe"
Then go to "File" -> "New Task" and navigate to the starcraft executable to run the game. Done !
Yeap, you will loose your desktop temporarily but you can bring it back up once done by running explorer.exe again from the task manager. No harm done.
Credits go to this website http://worms2d.info/Troubleshooting_FAQ#The_game_colours_get_all_messed_up