I have been having problems with my exchange backup for the last 2 weeks now. I have been getting error E0000821 and E000035E. The last 2 nights, I have been stuck with updating catalogs status. I cancelled it yesterday. Today, it has been going on now for 13 hours and the byte count has been stuck at 95,854,635,012 for more than an hour now. Everyday, it takes me a couple of hours trying to troubleshoot this backup issue.
I had a myriad problems setting up BE for exchange backups. It was a while ago now and the details are fading fast from my memory - however, when I too suffered overnigt backup issues it turned out to be related to exchanges own maintenance window. Sometimes I'd get the backup done, but mostly it would fail with different errors messages. Try adjusting your backup window, or, if that can't be done, move your exchange maint window out of the way of the BE process.