ok
make a system restore point
then click start -> run -> type regedit -> hit enter
search for and delete the following entries (depending on whether you just want to remove BtS or also the other two civ versions:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\{CFBCE791-2D53-4FCE-B3FB-D6E01F4112E8} -> just search for {CFBCE791-2D53-4FCE-B3FB-D6E01F4112E8} (Civ4)
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\{3E4B349F-10B5-4586-9D99-489A90A8B228} -> just search for {3E4B349F-10B5-4586-9D99-489A90A8B228} (Warlords)
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\{32E4F0D2-C135-475E-A841-1D59A0D22989} -> just search for {32E4F0D2-C135-475E-A841-1D59A0D22989} (BtS)
this should allow you to reinstall the game - if not remove all other entries with Firaxis Games (only if you don't have other Firaxis Games!) and Civilization in their name as well as other instances of {32E4F0D2-C135-475E-A841-1D59A0D22989} and the two other cryptic files above.
Before reinstalling (and I would recommend a clean reinstall of all Civ4 versions) do the following:
delete the games folder (i.e. the folder where the game is installed in - usually under program files\firaxis games\ ) and follow the instructions below:
Delete "...\documents and settings\<username>\my documents\my games\sid meier's civilization 4" manually
Delete "...\documents and settings\<username>\my documents\my games\warlords" manually
Delete "...\documents and settings\<username>\my documents\my games\beyond the sword" manually
Delete "...\documents and settings\<username>\application data\my games\sid meier's civilization 4" manually
Delete "...\documents and settings\<username>\application data\my games\warlords" manually
Delete "...\documents and settings\<username>\application data\my games\beyond the sword" manually
Delete "...\documents and settings\<username>\local settings\application data\my games\sid meier's civilization 4" manually
Delete "...\documents and settings\<username>\local settings\application data\my games\warlords" manually
Delete "...\documents and settings\<username>\local settings\application data\my games\beyond the sword" manually
(note: application data is a hidden directory so you need to configure windows explorer to show hidden files, also these directories in application data are sometimes removed by the uninstall routine)
Delete "...\Program Files\InstallShield Installation Information\{CFBCE791-2D53-4FCE-B3FB-D6E01F4112E8}" (Civ4)
Delete "...\Program Files\InstallShield Installation Information\{3E4B349F-10B5-4586-9D99-489A90A8B228}" (Warlords)
Delete "...\Program Files\InstallShield Installation Information\{32E4F0D2-C135-475E-A841-1D59A0D22989}" (BtS)
(note: InstallShield Installation Information is a hidden directory so you need to configure windows explorer to show hidden files).
Install Civ4, immediately patch it to 1.61 (download it fresh from
here)
Install Warlords, immediately patch it to 2.08 (download it fresh from
here)
Install Beyond the Sword, immediately patch to 3.13 (download it fresh from
here).