Exact same thing happens to me, Geforce MX4000, running latest Nvidia drivers.
I figured it was something related to pixel shaders.
Weird thing was, when I first launched Civ IV, it told me my pc was below the reccomended requirements.
I am running Athlon 64 3000+, 512mb, XP w/SP2, loads of hard disk.
It then turned all the graphics settings down to low. I turned them all back up to high, and haven't any slowdown issues at all until I got to fairly late in the game, and even then, my turns were taking about 1/10th the time the Civ III did.