Hello Ian,
What version of Exchange are you using?
Is it a local backup or a remote backup?
Does this error occur while backing up a single mailbox or multiple?
Are you using the Advanced Open File Option for the mailbox backups? If yes, then it is recommended not to use this option fro database backups like Exchange,SQL and Lotus Domino.
Stop the Antivirus if running and then verify the results.
You could also try creating a new user for test purposes,give it domain admin,local admin and Exchange full admin rights. Then try a backup.
=====================
NOTE : If we do not receive your reply within two business days, this post would be marked assumed answered and would be moved toanswered questions pool.