Nautilus searches through all the directories in search of places to put the trash... for big, network-mounted directory structures this isn't desirable: It should stop searching if you don't have write permission in the top directory.
Fixed in rawhide