I havn't run into this particular problem, but you can increase your AGP apature size in your BIOS to 256 and see if this fixes the problem.
The problem with black or missing textures tends to be caused when your video card runs out of memory and the drivers try to deal with the problem. With vanilla Civ 4(without Warlords), a 128 meg video card will generally have few problems with a 128 meg AGP apature size(128 megs of main memory are available to the vid card). With Warlords, this doesn't seem to be enough, so you need to go higher than that.
I've been fighting with this problem since I installed Warlords because pushing the AGP apature size to 256 megs leaves me with too little system memory in other games that I play, and I'll be doing a major system upgrade in a few months so don't want to waste money on adding more memory to my current setup.