If you change the password of the account you use to backup your machines (such as the domain administrator), then you also need to change the password in Backup Exec.
Backup Exec keeps a list of user accounts and passwords which get used to connect to the Remote Agent, known as Logon Accounts. The usernames and passwords have to be the same as a Windows account with sufficient privileges to back up the data. To test whether the Logon Account username, password and privileges are correct, before submitting a job you can test the credentials. It's a good idea to get in the habit of doing this before submitting a job. It's easier to discover the problem at this stage than the morning after your backup should have run!
To edit the password used for a user account, from the Job Credentials page, edit the credentials to match your updated password. Then test the credentials again.