I, too have been experiencing this same problem with CS4 running on Windows 7. In my case, I was trying to update a link to a PDF document.
I'm glad to know about the technique in which you browse for the file you want to link to, then first select another file, and finally double-click the one you really want. That does work for me, too.
I have just begun researching this problem, so I don't know if Adobe has anything on it. By now, both CS4 and Windows 7 have been out a while, so you'd think they would. IMHO, we shouldn't have to upgrade to CS5 in order for this to work.