Looks like backupexec has still stored your old password.
Open the Backup Exec Console, then go to Network -> Logon Accounts. In default configuration, you'll only have one item there, the System Logon Account. Select it, and click on Edit to the right. You'll be asked for a password, here I'm not sure whether its your old or your new password. Once you figured that out, you'll get the Edit Logon Credentials window where you have a "Change Password" button. There you can set the password Backup Exec uses to connect to its clients.
In case you cannot edit you current User, you will have to create a new one, set it as default, and delete the old one. Once you leave the Logon Account Management, Backup Exec will ask you to replace your old user with you new user in all jobs (which you should do of course).
I hope this helps