I fear in this respect this error message is probably right:
uninstall, remove anything that is left over completely (mainly the install folders you listed above, the stuff in ...\documents and settings\<username>\my documents\my games\ , the stuff in ...\documents and settings\<username>\local settings\application data\my games\ , the stuff in ...\documents and settings\<username>\application data\my games\ [the latter two are hidden directories and may or may not exist after the uninstall routine is done - set windows to show hidden files]) and finally before reinstalling
either rename the ...\Program Files\InstallShield Installation Information\ folder (could interfere with other installed programs!)
or click through the cryptic filenames in there (hey look like this:
...\Program Files\InstallShield Installation Information\{CFBCE791-2D53-4FCE-B3FB-D6E01F4112E8}
...\Program Files\InstallShield Installation Information\{3E4B349F-10B5-4586-9D99-489A90A8B228}
...\Program Files\InstallShield Installation Information\{32E4F0D2-C135-475E-A841-1D59A0D22989}
- problem is I do not know the numbers for complete edition - but you should find a file called setup.ini in most of them which tells you which program the folder belongs to) and delete the one(s) for civilization - would be nice if you could post which name those folders have

Finally finally

restart the computer before actually installing...
This would get rid of any lingering stuff that might interfere with the installer.
after installation check that the game works, then retry the 3.17 patch (no other patches will work - since complete is already patched to 1.74, 2.13 and 3.13)...