First, check to see if you have the setting in Tools | Options | Preferences, 'Display progress indicators for backup jobs' selected. if you do, before anything gets backed up, Backup Exec goes out and does a check of how much data will be backed up so you have a progress indicator in your job. I would recommend unchecking this if selected since it adds time to your backup.
Russ