On closer inspection, this issue seems to be restricted to sab processes started by the init script, and in recent ubuntu releases only. In a 10.04 vm, it still works all the way, but in 11.10 even when the user running the program is the same as the desktop user, it won't display notifications for a sab process started from init. When starting from a shell notify works with and without --daemon though, at the very least for the logged-in desktop user. I suspect this could be an intentional modification on the ubuntu end somewhere, or it's a result of differences in the process' environment, particularly the presence of certain environment vars related to Xorg.
*** edit: think I found the problem

***
mgori: assuming you are indeed running sab as a service, try adding "export DISPLAY=:0.0" to /etc/default/sabnzbdplus. Without the quotes, on a line by itself. The display is usually 0.0 - if not, find the correct one by running
echo $DISPLAY in a terminal. Don't know if this will work with processes started before there's any display active to begin with (i.e., the sab service on system boot), but at least it seems to fix things when restarting the service from the active desktop environment.