I went through this problem and wrote up my solution. YMMV, but I didn't need to reinstall the operating system. Note this was on Vista.
1. I downloaded BTS from Direct2Drive, but the install failed after "Setup is searching for updated DirectX Runtime Components and updating as necessary. This may take a few minutes..." - with a message like "The patch failed to install. Aborting".
I looked in the Windows event log and saw:
Failed to create restore point on volume (Process = C:\Users\Richard\Downloads\Civilization4BeyondTheSword_317_ddsetup\directx9\DXSETUP.exe /silent; Descripton = ôw; Hr = 0x80070057).
2. So, I disabled Restore Points (using the Control Panel) - remember to reenable these when your install is done (and you will lose existing restore points, which kinda sucks). Also note that you might be able to skip this step.
3. I re-ran the BTS install and got a little further. In particular I got to the message: "There is a new version of Sid Maier's Civilization 4 available the latest patch will now be installed." But then it failed again with the same: "The patch failed to install. Aborting" message.
4. I figured I would try installing the Civ4 patch myself - downloaded Civ4Patch1.74_Final.exe. Tried to install this. Got the error: "The setup has detected that no version of Sid Meier's Civilization 4 is installed. This update requires that a previous version of the application be installed." Aha, this seems to be the core problem.
5. Install Civ4 from CD.
6. Rerun Civ4Patch1.74_Final.exe. Now I get a message that "The setup has detected that version 1.09.000 of SM Civ 4 inst already installed. This setup is not compatible with this version. You will have to uninstall the previous version before installing this version."
7. OK, perhaps I jumped ahead too quickly. Download the 1.61 patch and install that. No problems.
8. Install the 1.74 patch. No problems.
9. Install BTS. I see a message about installing a patch for Warlords, but apparently my Warlords install was ok. BTS Install works.
10. Turn restore points back on.
11. Start BTS - enter activation code.
12. Game starts
So, what was so hard about this?

Civ4 is a great series with a nasty install. But the bottom line was that I had some type of corruption in my base Civ4 install and even though Warlords worked fine (I haven't played the base in a while) the corruption interfered with the BTS install.
Good luck all!
RB