FWIW, verifiquei minha instalação do Ubuntu 14.04 (64 bits) e tenho a mesma saída dpkg...
que você tem, além de alguns outros de outros aplicativos que estão sendo instalados.
Teste notify-send "summary" "body"
e também tente com --urgency=critical
para ver se isso tem algum efeito. O último é eficaz quando notify-send
está sendo suprimido porque um vídeo está sendo reproduzido.
Caso contrário, talvez instale um indicador de terceiros que tenha notificações e veja se isso funciona.
Encontrou o seguinte de um comentário em esta pergunta:
Tente limpar o daemon de notificação: sudo apt-get purge notification-daemon
e, em seguida, tente apt-get autoremove
. Certifique-se de que notify-osd
esteja instalado: sudo apt-get install --reinstall notify-osd
e reinicie.