Answer
Altiris Agents can be redirected to communicate with a new Notification Server by doing the following:
1) From the Configuration tab on the old server, go to Configuration | Altiris Agent | Altiris Agent Configuration
2) For each of the four configuration tasks list here go to the Advanced Settings tab and select "Specify an alternate URL for the Altiris Agent to use to access the NS", and then provide the new server name.
NOTE: You may consider cloning one of these tasks to test this with on a few machines.