Currently involved in a murder case (honest!) and house repair so will try and have a look at the problem in the morning
Does sound like an explorer or DirectX related issue from the cursory glance I've had.
Firstly worth checking your direct X setup.
From the Start menu choose RUN and then type DXDIAG and press return
This will then carry out the Direct X test - important to note the status/versions of the drivers you have installed (are they certified etc. and does the full screen option work correctly).
I also notice you haven't said what graphics card etc you have installed - I'd guess at a Kyro 2 based one as the Naturalcolor.exe line mentioned earlier seems vaguely familiar. Also worth mentioning what games are showing the problem.
Now off to bed before the girlfriend kills me