Проблема решена, если кому интересно, то вот порядок действий:
1. Удалить Symantec LiveUpdate. Если при удалении возникают ошибки, то удалить утилитой http://download.microsoft.com/download/e/9...1bd/msicuu2.exe и перезагрузиться.
2. Удалить папку C:\Program Data\Application Data\Symantec\Liveupdate или C:\Documents and Settings\All Users\Application Data\symantec\LiveUpdate в зависимости от версии системы.
3. Удалить папку C:\Program Files\Symantec\LiveUpdate
4. Скачать и установить последнюю версию LiveUpdate. Ссылка на версию 3.5: ftp://ftp.symantec.com/public/english_us_...3.5/lusetup.exe
5. Если LiveUpdate не видит BackupExec, то запустить следующее приложение с параметрами:BeUpdateOps.exe -AddBE –OptOut (находится в папке C:\Program Files\Symantec\Backup Exec\)
6. После установки некоторых патчей требовалось перезагрузить сервер (хотя сообщений никаких не было), чтобы установка остальных патчей прошла успешно.
После этих манипуляций проблема исчезла.
В поиске решения мне помогли эти советы:
http://www.symantec.com/connect/forums/bac...update-problems
http://www.techbind.org/category/Backup-Exec.aspx