If you are using Windows 7 try adding exceptions to DEP: Go to Control Panel -> System -> Advanced system settings -> Advanced tab -> Performance Settings -> Data Execution Prevention tab -> "Turn on DEP for all programs and services except those I select:"
If the list below will be empty, press Add and select D3DPopTB.exe and PopTB.exe

Just to be sure- you get the launcher with graphics settings, and the game crashes after you click the Launch button? Does it happen in both software and hardware mode?

You don't have to reinstall - just use the Setup shortcut from Menu Start. You can also try launching D3DPopTB.exe (hardware mode) or PopTB.exe (software) from game install directory.

Please contact our support and send your dxdiag report, and we'll take it from there.

It's not a bug, it's a feature :-P
Seriously though the idea is that GOGSetup either starts in setup mode (on the first launch, or if started through Setup menu start shortcut), or just starts the game on every subsequent run, so you don't have to click through the launcher every time.

This actually looks like the message from the launcher that fixes corrupted colors on Windows 7. It still means that the game executable crashed, but are you sure you launched game exe (PoTB.exe/D3DPopTB.exe) directly as wpegg said?

Also check if "run as Administrator" is set on compatibility tab for those two execs, not just GOGSetup.

And one more thing - if the game crashes, please write if that happens on software mode, hardware mode or both.

Actually the game has three registry keys that point to the install directory.

Try reinstalling the game, running the installer as administrator.

From what I see this happens if I remove the game registry key. Could you check if you have it?
It should be in HKLM\Software\Bullfrog Productions Ltd\Populous: The Beginning (or HKLM\Software\Wow6432Node\Bullfrog Productions Ltd\Populous: The Beginning on 64-bit systems)

OK, there could be two separate issues:
-"Missing or incomplete registry information" - for this reinstalling as admin should help, if not - check the game registry entries
-Problem on ATI cards - game is incompatible with recent drivers on most ATI cards, so an older driver is included. You can try renaming or removing atiumdag.dll in the install directory if that helps.