Error "Not on the same file system" while deleting

[Nick <niick blueyonder co uk>]

Hello,

I'm using Nautilus 2.16.3 in gentoo. A problem has recently developed
where i am unable to delete a file on a nfs mounted filesystem. I have
four nfs shares which this machine uses. All of them have been fine for
months, but now on one of them I can't delete any files. Using the
console & rm both root and user can delete. If I login as root then I
can use Nautilus to delete files. On the machine which serves the nfs
shares deleting using rm works fine (it doesn't have Nautilus). So its
only for a normal user in Nautilus. I've tried reinstalling Nautilus and
deleting ~/.nautilus, neither had any effect. I've googled around and
appartently i can workaround this by enabling permanent delete in
Natuilus. This is something I would really like to avoid, especially
since this was working perfectly not long ago.

Any suggestions are really welcome.

Thanks, Nick