well that is interesting ...
Would you be able to post the entire exchange DB backup log for analysis ?
Typically when HrESEBackupSetup reports an error it is matched with a corresponding error in the application event log, since the error is coming from the Exchange APIs
Can you confirm if there is any Anti-Virus software on this machine, and if the Exchange directories are properly excluded from any Anti-Virus scanner
Wearer of Many Hats