Yes, I have tried this. There are two old 'trusted certificates' that keep showing themselves within the Certificate Store; I will delete them and they come back after a few minutes. I have checked against the [Altiris] database to ensure there are no entries in there about these licenses that would cause them to be thrown back in. There is no instance of the licenses in the DB.
I have tried the suggestion of installing new certificates. I have deleted the old via MMC and via the Symantec license tool. I then installed new licenses which created new certificates. This didn't work. I then proceeded with a total reinstall of the OS,NS, and certificates. I admit this was a bit extreme but I have been in 'LIMBO' for 8 months with this licensing thing. Plus I saw this as an opportunity to upgrade from Windows 2003/NS7.0 to Windows 2008/NS7.1 Disappointingly (is this a word?) as soon as I installed the (freshly posted from Symantec licensing) licenses, the old Trusted Certificates showed back up in the certificate store.
Both the new licenses and the 'psuedo trusted certificate' contain the 'licensingca.altiris.com' entries. This is still an issue. While our proxy is no longer pelted with requests for the false certificate authority, there are still issues. The certificates are still showing as 'in error' with the 'A certificate contains an unknown extension that is marked critical'.
The NS is usable (thankfully), but the last time this happened, upon updating the NS with an MR, the licenses caused issues that installed mismatched versions for certain Suites and messed the system up in the first place. --And here we are [almost] 1 year later--