For those who ever have this problem, it is likely related to something getting corrupted in the user's logon profile.
We solved it by clearing the logon profile (annoying in itself, but not lethally so) - and hey presto, the open dialogues start working again.
Likely there is something screwy happening if the user has customised previous versions of Revit - in our case a user have customised the Library Folders in the open dialog (which aren't saved in Revit.ini - they are saved in th eregistry somewhere) and then upgraded to a 64bit machine (Windows 7-64) and Revit 2009 x64. The older Library customisations seem to have got scrambled - removing them from registry didn't solve the issue, but deleteing their entire profile (From Control Panel - System - Advanced) fixed it.
Do I get a solver's fee?