Quando você lixeira um arquivo que não está na mesma partição em seu diretório pessoal, é movido para o diretório .Trash-1000 na raiz da partição que você é. Certifique-se de que o diretório .Trash-1000 seja gravável para o usuário sob o qual você deseja eliminar o arquivo.
Eu também tive o mesmo erro, minha partição raiz era diferente do meu diretório pessoal - que é uma partição criptografada. O diretório /.Trash-1000 não era gravável pelo usuário atual em que estava logado. Resolvido executando
sudo chown MYUSERNAME /.Trash-1000