You do seem to be having a few problems. You could try the following for a comprehensive uninstall which may resolve your problems.
After testing Civ4 vanilla try installing Warlords which will patch vanilla to 1.61. Reboot afterwards. If Warlords works ok then you can try installing BTS which will patch vanilla to 1.74 and warlords to 2.13. If vanilla, warlords and BTS all work then you can patch BTS to 3.13.
Btw I'm assuming that you're running Win XP rather than Vista.
Good help Sam. I bought the regular Civ IV. Was playing it for a week and clicked on the updates option. Installed update 1.74 and the game would not boot. Uninstalled everything but the 1.74 patch and would not install 1.6 again because it kept recognizing 1.74. Didn't want to, but I went into the registry and deleted all The Firaxis files and then the {CFBCE791-2D53-4FCE-B3FB-D6E01F4112E8}.
I can now re-install Civ IV. No more updates