This user does not have sufficient credentials to access the database
Answer
This problem has been identified on installations that use the App ID to access the database. To work-around this issue without going through an NSSetup:
1- Go to the Database Settings page (Configuration -> Server Settings -> Notification Server Settings -> Database Settings)
2- Change the account from Application Identity to SQL Login (Fill in the appropriate contact information)
3- Go to the Application Identity page
4- Make the change to the Username / password (as applicable)
5- Go back to the Database Settings page and re-set it to use Application Identity