Eu tive problemas semelhantes, chegando até mesmo a colocar um atalho na lixeira do meu gerenciador de arquivos para que eu pudesse obter o espaço de volta. No final, a melhor solução para mim foi:
Use o pacote trash-cli
que pode ser instalado com sudo apt-get install trash-cli
e esvazia toda a lixeira de usuários com o comando trash-empty