If your using vista or later have you tried compatibility settings and turning off the desktop composition? If that works then it could be the same problem the worms game has where it uses the desktops colours or something like that and on vista machines this caused the game to have psychedelic colours as well.
Not sure why having the explorer window open would help though unless it took focus away from the desktop and gave it back to the game.
Just found the worms faq on the problem
" The game colours get all messed up
This happens when another application is stealing W:A's palette. W:A logs such occurrences to the file "palette.log" in your W:A folder. If you can, try closing the programs listed there.
Often it's a component of Windows itself that's stealing W:A's palette (usually csrss.exe). If you are using Windows Vista/7, having any Windows Explorer folder open while you play the game has been known to fix it. If this doesn't work, try terminating the explorer.exe process using Task Manager before starting W:A. You can later start it back from Task Manager (which you can open by hitting Ctrl+Alt+Delete), by going to File -> Run....
Another known work-around is to disable the Indexing Service and/or Automatic Updates services (Control Panel -> Administrative Tools -> Services).
You could also try an experimental WormKit module, which you can get here. "
kind of sounds exactly like whats happening in your game.