Here's the steps to follow from the KB article. Also make sure the latest SP is loaded.
Go to the Manage Software Updates Page. Highlight the failing update. Right-click and select Disable from the drop down. Then right-click and select Stage from the dropdown. Doing this will invoke the code that will ensure the updates are ready for distribution.
If you still receive this message even after working through this issue, then something is failing during the re-create process and the Altiris Notification Server logs should contain additional information. On the NS Server, go to Start/Programs/Altiris/Diagnostics/Log Viewer, and open the logs. Search for the update in question on the search field at the bottom of the logs.
A report is attached to this article which, after being imported, will return the list of all updates associated to the bulletin and whether they have been downloaded or not.