Installing notifications is not enough, you have to mount it using the site-map. Once this is done you should be find. Searching for "notifications mount" should have given you a list of postings hinting at that problem and saved you the waiting time till my answer.
P.S.: Isn't this behaviour fixed by Lars APM changes (checking a package is not only installed but also mounted, as is the case with Blogger and Forums for notifications) ?