A few items to troubleshoot:
1) Is Anti-Virus running in realtime protection mode? While not a great option, you might want to try disabling it and run a mailbox backup to see if it goes through fine. Sometimes AV interferes.
2) Any mailboxes recently set to Hidden or Deleted? These can cause backups to fail, usually with a "Directory is invalid" error however.
3) Turn your job logging to higher detail so you can see which mailbox is failing. (Tools\Options\Job Log) Is it consistently the same mailbox?