Nvm, after a lot of research I finally managed to fix all my problems and run the game smoothly.

To help others, it would be nice if you'd tell us what system you're using and what worked for you.

I have a Radeon HD 6970

Did a lot of different stuff to try to fix it, but in the end it came down to a few things.
First off I set the compatability mode to windows 2000 (this fixes the mouse and sound stutter). Then I shut down the explorer.exe process and launched the game, this fixed the colour issue in the menu. The colour issue still appears 90% of the time at the start of each new map, but I just swap resolution back and fourth until it fixes itself, so it's only a minor annoyance.

Thanks for letting us know. Depending on the Populous title, Aqrit's ddwrapper could solve the issues as well. (Try ForceDirectDrawEmulation=on and/or the ColorFix option)

Yeah that's one of the things I tried, didn't work. Just ended up with a black screen, could hear the sound etc in the background, but everything was black.