Have you checked this tech note?? this has in detail info on configuring the mail notification.
http://seer.entsupport.symantec.com/docs/254809.htm
Also as you have mentioned that mail notification is working except for one client which is newly installled.
Can you just check into Client's Host Properties and Click on
Server Sends Mail
Hope this helps and resolves you problem.