Você já tentou executar o nautilus como root e excluí-los? Execute o seguinte comando no terminal (use Ctrl + Shift + T para abri-lo):
sudo nautilus
Digite sua senha e tente excluí-los.
Para referência futura, sempre seja cauteloso ao executar o nautilus como root. As coisas podem ser quebradas com muita facilidade.