Hi,
Thanks for the replies. We think we're found our own solution and that is to re-install Backup Exec when we get this issue. One of the fixes posted above was to do a repair of the install, but this didn't work. You would have thought that a re-install was the same thing, but apparantly not. So far it has worked about five or six times, so fingers crossed it will keep working for us.
We had downloaded the fix a couple of times, but this made no difference. We also tried updating the version of Windows Installer, as we are using a very old one. However, even though it worked on the first server we tried, it failed on multiple following ones. The fix I've detailed above is working on servers without updating the Windows Installer service.
Thanks for the help everyone. I'll try stopping the SQL service as Freddy has suggested, if and when we get the problem again.
Nick