I have this problem as well. You can delete all of the files in your Program Files folder, if you try and reinstall the game it will say a previous version is already there. I think there is something wrong with the uninstaller. Basically I manually delete all the files and then you need to delete the registry entries.
To do this type in regedit and you will need to search the hkey_local_machine for files. I do a search for any files with "firaxis" in them and delete these files (which you have to do several times) and then the game will reinstall. I used to know the specific key, but lost that - it is posted somewhere on here as well, but I cannot find it right now. The above method works, just make sure the files you delete are "saved" in the recycling bin in case something else (another program) does not work...
