I have a work-around, if anyone's interested.
The problem (I think) is that the game needs to modify the files "c3.inf" and "c3map.inf" in order to save your settings, but can't actually write to those files due to directory permissions. The directory "C:\Program Files\GOG.com\Caesar 3" is normally where the gog.com version of the game installs, and is also where the game expects to be able to write to, to save your save-games and settings.
On Windows Vista/7 (I don't know about XP), anything in Program Files is write-protected, and as such, Caesar 3 can't write your save game files there. So, Windows does something clever to resolve this: it makes the game think it's writing to the above-mentioned Program Files directory, but it's really being redirected to a special directory somewhere in your Windows user-profile - the "Virtual Store", which is kept in "C:\Users\YOUR USERNAME HERE\AppData\Local\VirtualStore".
So the problem is that when Windows intercepts Caesar 3's attempts to write its save-games files, it works, but for some reason, not with its settings files (c3.inf, c3map.inf).
SKIP HERE IF YOU JUST WANT THE FIX.
Here's the lazy and hack-ish work-around:
Right click the desktop icon for the game (or whatever you use to launch Caesar 3), and hit "Run as administrator". Start a new game (if you try to load a game, you'll see all your save games are gone; this is normal), change whatever settings you need to, and then exit the game. Re-launch the game as you normally would (ie, not as an admin), and you should now have the settings you want.
Do note that if you want to change your settings again, you'll have to run the game as an admin in order for them to persist.
The other solution is to copy and paste your save-game files from Caesar 3's VirtualStore directory into its Program Files directory, and always run the game as an admin. The game will no longer write to the Virtual Store, but instead, exclusively to its Program Files directory, with full write access for whatever files it needs to write.
Thanks.
Edit: Clarified a few things.
Post edited March 27, 2012 by Bapabooiee