Without knowing ANYTHING about this, my first guess would be, "What other schedulers are being used, and how do they conflict with it?"
I mention this because "auto backup" to me screams "SCHEDULER!" and therefore "CONFLICT!"
Can you do a Backup manually? Does it crash at the same point, if so?
Can you locate other schedules you've got doing automated things (AntiVirus updates, Windows Updates, Java Updates, Browser Updates, Flash and all Adobe Updates, iTunes & Apple Updaters, and every other Updater - SKYPE? Twitter-Facebook, ICQ, etc, running constantly?) and turn them off or shut them down?
Then, try a Manual Backup and see if this changes its failure/success.
If you shut everything down and the Backups work properly (auto as well as manual), then I'd probably think "So this is a scheduler conflict - some program's scheduler either hates Samsung's, or the events are in-conflict and maybe I can adjust them to avoid each other."
The Cleaner you used might have been a participating culprit but there's a chance it removed Registry Entries that allowed other products to tailor themselves, so reinstalling Samsung-Backup obviously didn't fix that problem. That was an excellent tactic, though, on your part. (Registry Entries can be affected by First Value Read vs Last Read for conflicts.)
I'm hoping "Schedule Conflict" is the problem. That's the easiest 'fix'.
If it's a Samsung program error, then it's likely to be based on "how are open files handled, or how unbackup-able folders-files are handled." This would be a bug and they should be made aware of this for a later fix. In other words, "no quick fix".