Константин, в итоге нашел решение сам, вся сложность была в подборе правильного поискового запроса.
Есть два типа проблем:
1. Не удаляются (в корзину) файлы из папки home . В этом случае наиболее часто у папки корзины стоит владелец root и его нужно сменить на текущего пользователя.
2. Не удаляются файлы из корневой директории "/", в том числе "/var/www", тогда проблема в том, что папки корзины (как правило "/.Trash-1000/") просто не существует, а текущему пользователю не хватает прав, чтобы её создать, и создать её нужно под рутом ручками.
У меня было второе, решил проблему здесь -
http://forum.ubuntu.ru/index.php?topic=260597.0