First, identify which revision of Backup Exec you're using ... Help > About, and look for the 4-digit number. If it's 11.0.6235, I recommend upgrading to Rev.7170, found here:
http://esdownload.symantec.com/akdlm/CD/MTV/BEWS_11D.7170_32BIT_VERSION.zip
Next, are you backing up the Exchange 2003 server or the information store, or both? Based on your closing comment, it sounds like you're backing up everything on the server in a common job. A common problem we encounter are users who are backing up the server AND the information store, and we see the \Exchsrvr folder (or a specifically customized database or logs location) selected for backup as well as the information store. That would represent a conflict and could cause jobs to fail. In this case, it wouldn't matter if your credentials are correct, you'd be performing a backup of the file at the same time you're performing a backup of the information store and BOOM! Access denied.
The best recommendation is to separate your jobs by agent type: back up the data portion of the Exchange server separate from the job that backs up your information store.