Running notify-send hello terminates normally with no errors visible anywhere, but I don't see a notification. I've noticed this on several installs across multiple machines. I'm guessing it has something to do with some piece of configuration I do personally since nobody else seems to have this issue.
I just checked, and on a fresh user account with no theme changes notification works.
Found the problem: If you have a gnome terminal that you have full-screened with F11, the notifications don't show. To an extent that might seem correct, but they don't show on /any/ workspace, even if the current workspace has no full-screened windows. Moving and modifying...
I can't reproduce this with metacity; but my guess is that this is a bug in the interaction between libwnck and compiz, because how compiz does workspaces/desktops is "special". Look at src/daemon/daemon.c:fullscreen_window_exists in notification-daemon.
Problem is gone in F10. Should we call that the end of it?
<stamp> THE END.