Do you have the Exchange Agent installed on the machine running Backup Exec Server? You can check this by going to Tools, Serial Numbers and Installation... and selecting local install - additional options.
You will need a licence for the Exchange Agent in this case then. If you already have one, you will need to input the serial you have into the area mentioned above to install this.