When are you running these backups? By the sound of it you're doing them during the working day which I would suspect is where you're problem is. My suggestion to you would be to change the schedule to run them during the night when no one will be connecting to Exchange to be effected.
Consider that to do a mailbox backup, Backup Exec uses Outlook to open each mailbox in turn, and reads each and every e-mail to back them up. Now remember that this is all happening at a very fast rate, much faster than than any one or several users could interact with the system, and you can see why it would be putting a lot of load on to your server, and therefore causing connection problems / Outlook freezing for your users.
By comparison, where I work we have quite an old low powered Exchange 2000 server, used by only 7 people, but with a LOT of data stored within it (around 30+GB), all it takes is someone on the network to do a big search on their mailbox and everyone sees their outlook freeze (which would be why we're in the process of upgrading that box).