I have just tried to use notify-send on my 13.10 machine and can't get it to work without using sudo with it.
I don't know what details can I provide with this issue.
My notify-osd version :
$ ii notify-osd 0.9.35+13.10.20130917.1-0ubuntu1-leolik~ppa0 amd64 daemon that displays passive pop-up notifications
On regular version for 13.10 there was the same issue.
EDIT
$ ll /usr/bin/notify-send
-rwxr-xr-x 1 root root 14720 wrz 10 16:12 /usr/bin/notify-send