Running Populous The Beginning in either D3D or regular, I get funny colors on the main menu and in-game.

The game was working fine before, but I decided to re-download to get the Undiscovered Worlds addon, now I always get funny colors.

Basically the whole screen turns 'rainbow' and it makes it completely unplayable.

Was looking forward to playing this great game again.
Nobody knows a fix for this?

Thanks in advance,
Vincent

EDIT:
Playing around with it some more D3D suddenly doesn't have the colors, but it has issues just as bad.
A flickering mouse (even after trying my mouse fix) and graphical artifacts in the text and on sprites and stuff.

I haven't played the gog version much, I just started the first level.
As far as I know, I got only the glitches in the menu (colors and mouse lag), but ingame was everything fine.

I tried then a fix from the gog forums and I got normal colors and fluent mouse controls in menu.
But ingame the colors were messed up.

So I wanted to re-download the game and play it without any fixes. But I didn't get to it.
I will start the download right now and I will post my results.

Did you had configured someting with the game or did you tried to play the game without any tweaks?

EDIT: Everything works fine. Started the game via GOG Launcher after installation and the desktop exe, both as admin. (D3D Versions)
Sounds is a little bit messed up, mouse lag in the main menu exists. But I had no colors issues. I got them only back then, as I tried to fix the mouse issue.

Take a look at this thread, does it help you?
http://www.gog.com/forum/populous_series/severe_graphical_glitches_sound_stuttering_and_mouse_lag

EDIT 2: Here my system:

Windows 7 Home Premium 64bit
Intel Corei5 2500K @ 3,30 GHz
Nvidia GeForce GTX 560 Ti
8 GB Ram

What graphics card do you have?