Ce message apparait car, si vous allez voir dans le dossier /var/run/, il s'y trouve un fichier reboot-required
Dès que ce fichier existe, le message demandant le reboot apparaitra dans le motd. simple non ?

Ouais mais maintenant pourquoi faudrait il redémarrer la machine ? encore plus simple : suite à une mise à jour de paquet. via aptitude :D
Afin de savoir quel est le paquet concerné, il faut regarder, toujours dans /var/run/ le contenu du fichier reboot-required.pkgs

Par exemple, je viens d'effectuer quelques mises à jour sur ma machine, et ce message apparait.
En allant voir le contenu du fichier, je vois libssl0.9.8
En effet, cette mise à jour ne peut être "active" tant que l'on a pas redémarré...

bref, j'espere que ca pourra vous éviter de tourner en rond en vous posant tout le temps cette question ;)