We had installed before Symantec added a step to their best practice for upgrading, which dealt with granting permissions for the database, and released the instructions for if you had skipped the step (though, by the point we were at it didn't help as the error had went away, though we were having problems such as the one listed). To fix, I first ran aexconfig /configureall from an administrator command prompt (located in Program Files/Altiris/Notification Server/Bin). This took around six hours to complete, but opening the Altiris log showed A LOT of items that had not been registered, and A LOT of bad tables/entries that were being dropped. After it was all set back up the way we wanted it, the computer(s) appear again, but had to recreate the preboot environment before it would accept a job, and then it worked.