solution

[Daniel_Lyza_2]

I had a very similar problem to you, so I called Symantec Tech Support. 

This is what they told me: make sure the file beremote.exe on both the Backup Exec server and on the server you are trying to backup is the same version.

I had version 11.0.6235.0 on the server I was trying to backup and 11.0.6235.14 on the Backup Exec server.  Pushing out the new Agent to the server fixed my issue.

[Daniel_Lyza_2]

oops...The original post said the user was getting the following error:

The Exchange Store service is not responding. Backup set canceled.