The problem of the palette getting stolen by another program never happens to me ingame. However, it happened to me when I tried to watch a recorded replay.
I had just manually exited from another replay, and I had tons of other programs open. I opened the replay, and the 3D piechart loader showed up in messed-up colours. The replay also had messed up colours. I exited from it, and tried to view it again. The same thing happened. Then I opened W:A and started a game to see if the same thing would happen to that. It didn't. I exited from the game, opened the same replay I had been trying to view, and there was no palette problem.

Rule of gaming, Don't multi-task when gaming.

What does palette.log say?

Rule of gaming, Don't multi-task when gaming.
I wasn't multitasking.

There is no palette.log.

having multiple programs open = multi-tasking (you have multiple tasks but giving priority to one?). programs can lock certain resources causing other programs to fail which is why pretty much every games readme these days says to not run the game while anything else is running.