É o crontab do seu usuário, não o crontab do root?
Sugiro que, pelo menos para depuração, você crie um script como John T descreve:
* * * * * /path/to/script.sh
Veja como o script pode parecer:
#!/bin/bash
{
echo "trying to notify at $(date)"
DISPLAY=:0.0 /usr/bin/notify-send -t 1000 Test "This is a test"
echo "finished notify at $(date)"
} > /path/to/your-notify-debug.log 2>&1
Note que não há ":" antes do DISPLAY, como você parece ter na sua pergunta. Certifique-se de tornar este script executável ( chmod +x /path/to/script.sh
) e deixe o cron tentar executá-lo algumas vezes. Em seguida, examine o que foi gravado no arquivo de log.