I had a similar problem when we upgraded to Exchange 2010 SP3 and the steps outlined above worked for me........ thanks for posting it !!
AJ
28 Apr 2013 1:00 PM
Phil
8 Aug 2014 11:26 PM
The same issue after RollUp 6 . Deleting the backup directory worked fine.
Thanks