Sandi,
I have a few questions for you.
What version of Exchange?
When you enabled legacy support, were you able to drill through all of the mailboxes?
Can you back up the IS to disk with out error?
The Exchange account needs to have certain rights that the Domain Admin account doesn't have by default.
Here is a technote that describes exactly how the account needs to be set up:
The most common error that I have seen is hiding the account from the address book, the account you use for your backup can not be hidden.
Thanks.
Patty