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.