This is not like one of the cases addressed before - I've checked them all.
I've suddenly begun getting that message "... can't be put in the trash. Do you want to delete it immediately?" this morning in my Home directory only.
I have a Home partition (ext4, mounted properly) with symlinks for user folders like Downloads, Documents, etc. to folders with the same names in a Data partition (ntfs, mounted properly).
For example, I cannot move a file in Downloads folder to Trash when I try via Home, but no problem if I try via Data partition, although the file in question has the same ownership and permissions at both locations.
Also no problem at all with files in my Home folder, including sub-folders like
Public that are not symlinked to my Data partition.
Interesting puzzle for me...
PS: Just upgraded to 15.04 but I don't think it matters... On second thought, it might perhaps be something to do with upgrading from Nautilus 3.10 to 3.14?
PPS: This bug has been finally resolved some time later in version 16.10, and no longer exists under Ubuntu 17.04.