Talvez tente reinstalá-lo com: sudo apt-get purge notify-osd && sudo apt-get install notify-osd
Acabei de tentar usar notify-send
na minha máquina 13.10 e não consigo trabalhar sem usar sudo
com ele.
Não sei quais detalhes posso fornecer com esse problema.
Minha notify-osd
versão:
$ ii notify-osd 0.9.35+13.10.20130917.1-0ubuntu1-leolik~ppa0 amd64 daemon that displays passive pop-up notifications
Na versão regular para 13.10, houve o mesmo problema.
EDITAR
$ ll /usr/bin/notify-send
-rwxr-xr-x 1 root root 14720 wrz 10 16:12 /usr/bin/notify-send
Talvez tente reinstalá-lo com: sudo apt-get purge notify-osd && sudo apt-get install notify-osd