I had the same problem with the upgrade, everything seemed to run fine, but when I re-opened Outlook (2007 on Vista 32), CC wasn't there. When I checked the addins, there was an entry for CC, but it was on the inactive addin list. I then went to my com addins, saw the CC entry with no check box next to it and checked it. I then saved and exited out of Outlook.
When I got back in, still no cc. I checked addins again and it was still in the inactive application list. I tried checking the box again, which worked, but this time, I didn't exit Outlook, I went directly back into addins and CC was still on the inactive list.
I then went to Programs and Features, saw CC as an entry, I tried to repair it, but it couldn't find a file. So I uninstalled it and then reinstalled v. 4. No errors or problem reported. I opened Outlook and still no CC toolbar. I went back into Trust Center|Addins and saw cc was still on the inactive addin list. I opened my com addins and then deleted the cc entry. I exited Outlook.
When looking at my installed programs, CC v. 4.0 was listed, but when I looked at the source column for it, I saw the file it was looking for was in the same directory that showed up when I tried to repair it earlier (c:\users\...\AppData\Local\Temp\IXP000.TMP\). When I went to my Local\Temp directory, I did not see the subdirectory IXP000.TMP. I left that explorer window open and reran the install.
After the first phase of the installation (file extraction), I was presented with the window asking me to continue with the install. Before I clicked yes, I went back to my local\temp directory and saw IXP000.TMP, which now contained 2 files, clearcontext.msi and setup.exe. I copied those two files to my desktop and then continued with the install. Unfortunately, that didn't work. Now inside Outlook, cc didn't appear anywhere in my addin list.
I then copied the two files (clearcontext.msi and setup.exe) that I put on my desktop into my user directory (c:\users\...\AppData\Local\ClearContext). I reran the setup file from this location, but still no cc. However, this did succeed in changing the source location of my Clear Context entry in the Programs and Features (btw, this is the new name the old Add/Remove Programs in Vista). At least the installed app was now pointing to a file that actually existed.
I went back into Outlook, opened Trust Center|Addins and opened my com addins, still no cc entry. I then clicked Add and navigated to ...\Local\ClearContext and clicked on setup, but that didn't take.
I then reboot the machine and tried installing cc4 again, but no luck. It shows up in my Programs and Features but not inside Outlook. I also disabled all of my other Outlook addins and tried again, but still no luck.
After 3+ hours, I'm going back to the earlier version. I have included all of this here in the event it might help you guys figure out the fix.
P.S. I forgot to mention that I also deleted the temp folder contents before rebooting hoping that might fix something, but still no joy. I did notice one additional weirdness, when I tried to reinstall after removing and rebooting, the installation window aske me if I wanted to "resume" the installation, which wss weird since I (thought) I had completely removed all traces of the former install. I hope this helps.