It does work out-of-the-box here, installing and playing on a clean prefix.

Debian Sid
Wine 1.5.30

If you are trying to install it on your global prefix ( ~/.wine ), you should create a new clean one for that game.

"mkdir -p ~/.wine-prefixes/caesar3"
"export WINEPREFIX=~/.wine-prefixes/caesar3"
"wine …"

If it does work, you'll have to create a launcher to tell wine Caesar III should be launched from its own prefix.
Here is my launcher, you'll have to change the paths to the one you used on your system :
"#! /bin/sh
export WINEDEBUG=-all
export WINEPREFIX=$HOME/.wine-prefixes/caesar3/
cd /usr/local/games/caesar3
wine c3.exe"

I think you have the same error as in the Mac thread - try this solution:

http://www.gog.com/forum/caesar_3/caesar_3_on_mac/post9

(solution reposted by fenij in the next post)