Não sei por que não está funcionando para você, talvez porque ele seja executado antes que o Unity esteja totalmente carregado. Você pode tentar adicionar um atraso de tempo usando o comando sleep
.
Eu consegui trabalhar criando este script:
sleep 2s
notify-send "Hello User" "Welcome back to Ubuntu 12.10" --icon=/usr/share/unity-greeter/cof.png -a "Computer" -u critical
Salve isso em um arquivo, defina-o como executável usando chmod +x <filename>
e adicione-o à sua lista de aplicativos iniciais.
Se isso não funcionar, tente aumentar o atraso antes que o comando notify-send
seja executado.