First, if you enable the legacy backup method can you backup all mailboxes?
If not then you have an issue with security on the account you are using. There are certain rights that are needed to backup the IS.
The following technote explains what rights are needed:
The one thing most people overlook is the account being used to back up the IS needs to have a mailbox and can not be hidden from the address book.
If you can backup the mailboxes with out a problem then the issue will lie with MAPI. Depending on if you are backing up to tape or to disk will tell you what server has the MAPI issue.
Have you tried backing it up to disk? Does it work? How about to tape?