I have Service Pack 1, and Hotfix #7 installed, so no this isn't a case of not reading the release notes.
I also have had the same problem with installing Service Packs, and various other Hotfixes on these servers in the past. I had to reinstall Backup Exec a number of times before I could get the Service Pack on a lot of our machines.
Thanks for info about 5520, when looking for updates for Backup Exec (since the Veritas Update page is broken) I was only looking under "patches" or "upgrades" not under "install".
The correct link for 5520 is http://seer.support.veritas.com/docs/277181.htm
as a side note, ftp.support.veritas.com is down, so getting 5520 is impossible (verified from 4 ISP's)