Was the file actually deleted?
Does a disk utility such as Check Disk indicate that your hard drive is healthy?
Do you have enough free space on your drive?
When this occurs, are you able to manually remove the directory? Is it possible another process such as backups or antivirus could be accessing the old backup files?
Never thought about other process in conflict. It always happens about the same time as another system back-up.