If you are seeing the same thing with the legacy method, try using MFCMAPI to attach to the mailboxes that you cant see. This will help determine if you have problems with mapi on that server. BE does rely a lot on MAPI working properly.
However, what you're describing does sound like an issue that Symantec is working on... but the issue only affects GRT mailbox restores to tape drive only. Backups to disk, and legacy mailbox backups work as they should.
I do not have any issues with my exchange and I do backup to tape. I still backup the mailboxes as well, mainly because I have plenty of room on my tapes and plenty of time to perform the backup, I understand that not everyone has that luxury.
I originally had heaps of problems but in the end I removed all the carry over backup selection lists and jobs that were carried over from V10, as well as all the pre installed policies so that my pallette was blank. I then created a new selection list and lo and behold, it worked.