try this first, is this a cluster environment if so this can be little more tricky then normal?

http://social.msdn.microsoft.com/Forums/en/sqlnotificationservices/thread/0f2fe589-65fb-4462-812e-a7fddcfcc017