В чем крылась проблема нашел(напишу, вдруг кому пригодится).
При запуске ритмбокса от рута - все прекрасно удалялось, что натолкнуло на мысль о правах. Когда посмотрел на права на эту папку с треками, то изрядно удивился, увидев владельца - рут, а не текущий пользователь-админ(хотя с правами не игрался). Попытки сменить владельца ни к чему не привели(владелец автоматически сменялся на рут, хоть убей).
Но мне повезло, что как раз систему надо было переустанавливать и после переустановки все сразу стало нормально. Владельцем стал текущий пользователь, а не рут и файлы спокойно улетают в корзину.