CCleaner did the trick for me too!
But I still suspect something about CS4 installer is not right.
Under CS3 I used Vista "open with">"choose program">"always use" to assiciate bridge CS3 with my canon camera raw files.. At that time it did work.
After installing CS4, I wanted to do the same with bridge CS4 but it didnt work. In the "choose program" vista menu, whatever I was doing, I couldnt select bridge CS4 it was always comming back to photoshop cs4 or bridge cs3.
After using CCleaner, I could re-associate the way I want right away.
So my word to photoshop's installer developper: please try to reproduce this issue, it should be easy, and make the installer avoid this.
Thanks