I'm having the same problem with 'Disk Cleanup' failing when initiated via 'System Tools'. It works when initiated through the C: drive's property window.
I've had identical failures on 2 new Dell Precision M2400 machines, even when NO other software or devices have been loaded.
Dell is stumped...
Any one find a solution yet?