I've just upgraded my machine, and I also experienced problems installing. Since there doesn't appear to be much info here specific to
Civilization IV : Complete I thought I'd share how I got it working.
The Problems: I followed kiwitt's guide as much as I could, ie, changed install folder ("D:\Programs\CivilizationIV"), ran setup as administrator (only one "setup.exe" on DVD), etc.
I then found that I couldn't apply the patches properly. The Vanilla and Warlords patches complained that I didn't even have those games installed, and the BtS 3.17 patch worked but the 3.19 patch failed to run at all.
My Solution: I believe the Vanilla and Warlords problem was solved by the fact that the BtS 3.17 patch already included Vanilla 1.74 and Warlords 2.13. So it seems I downloaded those patches for nothing.
The BtS problem was surprisingly solved by using the in-game updater of all things. After manually applying the 3.17 patch I had downloaded, I made sure I ran BtS as Administrator (through right clicking .exe->Properties). The in-game updater worked for me without a hitch. I guess miracles do happen!
Have since installed the two HOF mods + BUFFY, and since the HOF AssetsChecker is happy, I'm happy
Regarding Colonization, I'm sorry I can't say anything about this as I don't have it. My "Complete" was Vanilla+Warlords+BtS.