Can't move files to trash without any permission issues

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.

This is a bug in nautilus, since the same doesn't happen in Trusty (as you found out by yourself); the explanation for this behavior might be that nautilus always tries to delete the files reached through the /home path as being physically located in the /home partition even when they're reached through a symbolic link to a folder physically located in another partition: in this case "trashing" the file like usual fails because the target file cannot be be moved to the user's Trash, hence the prompt to delete it immediately instead.