Maybe it's being locked by something. Try unlocking the folder (from it's process) with this: http://lockhunter.com/

Or maybe HD is messed up. :P A folder not deleting at all happened to me before.