Hi Priya,
Thanks for responding.
Unfortuantely, I had already tried deleting all the logon accounts and recreating the System Logon Account which happens to be the same as the Backup Exec service account anyway.
In the end I decided that Backup Exec's account database must have some sort of corruption. I believe there are tools to address this situation but, under the circumstances, the most expedient way to fix it was to uninstall Backup Exec and re-install it. This worked a treat.
Thanks again,
Martin.