I was having an issue where any gnome-vfs enabled file selector would take several minutes to appear. This issue had been bugging me all day, as it would take nearly five minutes to do a simple save in the GIMP.
After a frustrating time to figure it out, I discovered that there was a URI pointing to an IP address that no longer existed in the ~/.gtk-bookmarks file. After removing that line (which did not show up in the file selector, by-the-way), everything returned to being appropriately zippy.
If you are also having the same problem (at least a few other people I have talked to seem to have seen this issue before), I highly suggest editing the .gtk-bookmarks file and remove the offending the line.
Update: Martin, thanks for pointing out the link to the bug in Bugzilla. (: