Update your graphics card drivers.

Updated drivers - Same thing happens. (I must not have been clear when I said "Problem is not game specific it happens in every game I try" I meant to say in DOSbox.)

Went into config and set to start dosbox directly in fullscreen - I thought I found a solution but shorty after that the same thing happens during normal gameplay.

Try different output= and /or set the sdl_videodriver=windib variable.

That's quite the sentence.

Mind rewording it for noobs?

Open a command prompt:

Type in: SDL_VIDEODRIVER=WINDIB

Launch DOSBox from the same command prompt you just typed the command in.

Also open your dosbox.conf and change output= to different values.

That's all the noob rewording you'll get from me.

Also see the following thread:
Full-screen colour problem

This is a widespread Vista/Win7 issue.

Other ways to fix it:
- use output=opengl or openglnb instead of surface or ddraw (my preferred method, since it's the most painless)
- kill all instances of explorer.exe in the task manager before launching the game (necessary for old 256-color windows games like Starcraft)

output=opengl fixed it

Thanks