This has been going on for at least a week. There are multiple threads here about it. I was hoping for an answer, or at least a fix.
One update applied itself on my Samsung Galaxy S3, everything worked perfectly for one day, and then this morning the out of space error was back.
Enough already. I've uninstalled the Backup and the main Avast! app. I've put way too much time into trying to figure this out on my own, and clearly no one at Avast! gives a damn about answering any questions.