The internals of wall and are so blocked off and ancient that there's really no way to pull the message from it once it's in there.
The only real idea put forward for this (the problem has been discussed before, many times) is to alter the shutdown and reboot scripts so they either make something available via dbus or (as we're only dealing with one computer and one fix) you could just have it send a notify-send message.
They are just scripts so you could just hack into them. But I think this is probably a cause worth pushing for. Submit a bug against Ubuntu and add your patches (just make sure they can work without needing to send the notification if there's no X environment). It's this sort of usability that we need.
I've never heard of gxmessage before, but I would use notify-send.
A full solution would need to cater for the possibility of multiple displays (eg multi-head, remote users, etc) but thankfully I wrote some code for that bit yesterday:
for display in `ps aux | grep -oE "/usr/bin/X\s[^ ]+" | cut -d " " -f 2`; do
DISPLAY=$display notify-send -u critical 'Shutdown notice' 'Save all your work. THE SYSTEM IS GOING DOWN!!' -i /usr/share/pixmaps/gnome-computer.png
done
(I'm using export instead of a -display or --display flag because I don't know that notify-send takes either)
libnotify-binpackage. – badp Nov 11 '10 at 14:24