По крайней мере, в Ubuntu 13.04 и выше (не совсем точно, когда был сделан переход), любые файлы, удаленные в nautilus при запуске от имени пользователя root, могут быть найдены в:
/root/.local/share/Trash
Фактические файлы будут быть в каталоге files, а некоторые дополнительные данные (которые хранят информацию, например, когда данные были удалены, и их исходное местоположение) можно найти в каталоге info.