Pues no sé si existe algo similar y más "bonito" en gnome, pero si tienen abierta una terminal, lo que buscas es wall (si no la tienen puedes convencerlos para que lo hagan ;-) ).
Ya puestos, mejor un servidor jabber, no? Y envias los mensajes a tuservidor.tld/online. Así tienes la ventaja (según se mire ;) de que tus usuarios podrán responderte.