I tried both of ellie's suggestions, and neither of them worked.
I ran the DirectX setup on the CD manually and during the install... Both times it said that updating had completed.
When I uninstalled the driver(it was called 'ATI Display Driver'). I had to reboot before I could install the drivers I downloaded(something about needing to setup the card as a standard VGA adapter before it could install). Once it rebooted, I installed the driver and rebooted again. Tried to run Civ and got the same error.
One thing to note is that when I start the game, it runs through all of the little XML Init/etc... and it tries to change the screen resolution about 5 times(the monitor "clicks" each time) before giving me the error message. Oh, and the mouse pointer changes briefly to what I assume is the Civ4 pointer(a golden ball with a squiggle through it).
I have an ATI X800xl(256 MB), and AMD 2400+ w/ 1GB RAM.