Shukaku: Try doing this:
1) Start -> All Programs -> GOG.com -> Populous - The Beginning -> Setup
2) Select Hardware Mode and 1280x720 @ 16bpp
3) Save Settings.
4) DO NOT LAUNCH THE GAME FROM THIS WINDOW. Close down the window by pressing X at the top right of the window. You'll probably get some message about incompatibility, just click cancel to this.
5) Start -> All Programs -> GOG.com -> Populous - The Beginning. Right click the shortcut Populous - The Beginning inside the folder you opened and click "Open File Location"
6) Double click the D3DPopTB.exe executable.
The game should now launch. If not, please post back :)
I did those steps, however 1280x720 @ 16bpp is not available, only the same option with 32bpp. I selected that option and hit "Save Settings", then tried launching exe with no success. Went back to settings and checked and it does not appear that the 1280 was selected, and when I hit save settings nothing happens. I change, close out, go back, and it's right back to the original resolution option 1366