Just a small update, after searching the KB for related topics I came across this technote: http://support.veritas.com/docs/254460
After reading this, I have come to the conclusion that maybe the Domino agent isn't installed on the server I require backing up. The agent IS however, installed on the backup exec server.
What I was a bit reluctant to do, was follow these instructions as it appears to mention a re-installation of Backup Exec server. Won't doing this cause a problem with everything I have already setup on the backup server?