If you would like another way to send a message to everyone, use the net send command from a cmd prompt. Your workstations must all be running the messenger service. Look in control panel, services and see if messenger is running on the workstations. If your workstations are Win9x you will have to be running winpop up for them to work, its not setup by default.
net send * This is a test
will send a message to every workstation in the domain running messenger or winpopup.
See Q168893 for more information on this topic.
I have also seen when workstations are setup with more then one protocol, issues like this. Yet another reason not to install every protocol until it works, Im not saying this is your case but Ive seen people install everything under the sun and the binding orders get out of whack. If by chance someone installed all your workstations with Netbeui, TCPIP, IPX/SPX or you need all these services, make sure they are all using the same primary protocol in the binding order, this will fix lots of other issues like long time out's when accessing network resouces.
Pete