Comment 3 for bug 819506

This is strange indeed, as both notify-osd and notification-daemon get D-BUS activated when needed. What could happen is that they crash when being activated the first time, which would give the "The name org.freedesktop.Notifications was not provided by any .service files" error.

I could paper over this in Jockey by catching and ignoring the error, but that would just hide the actual problem. Do you get a crash of notify-osd in /var/crash/ and/or dmesg when this happens?