Let me know the settings you are using: delivery method (smtp, netsend, mapi, etc) recipient type, per job notifications or global alert notifications? etc.
From there we can probably come up with a few items to check.
Another thing, aside from notifications, are all jobs and other functions still working properly?