Well, that was not the case here. As a matter of fact, the problem was related to the upgrade. Apparently, in my case, upgrading from Live State 3.0 to 6.0, then 6.0 to 6.5 and 6.5 to 7.0 left lots of junk in the registry that was causing this particular error. The cleanup scripts did not help much either. What fixed the problem was a good registry cleaner which deleted all references to classes with missing files.
Now, the backups run BUT they run so slow that they are unusable. For example, the estimated completion time for a 60GB backup over the network clocks at about 35 hours. I have a case open with Symantec and, hopefully, someone will be able to figure it out. NTBACKUP, on the other hand, completes in about 2.5.
So, I'm not upgrading any of my servers, or other workstations, until I get a resolution to this issue.