Did you change the password directly on the services themselves or via the steps here:
http://seer.entsupport.symantec.com/docs/283722.htm
How to change the Vault Service Account (VSA) or reset its password when using Enterprise Vault (EV) for Microsoft Exchange
Details:
In order to change the VSA or reset its password, perform the following steps:
1. Logon to the EV server as the VSA.
2. Open the Vault Admin Console (VAC).
3. On the Directory container, select Properties and click on the Service Account tab as shown below. (Figure 1)
Figure 1
4. Reset the password for the VSA, or click Browse to change the service account. (Figure 1)
5. Click OK when the next window comes up.
6. Restart all services.
Note: To change the VSA to another account, make sure the new account has the correct Active Directory (AD) group membership along with SQL (db_owner and db_creator rights for all the databases) and Exchange (Exchange Full Admin) Permissions.