Bonjour Instant Messaging, none can see each other or message each other at all.

I am trying to use Bonjour Instant Messaging to communicate around work. The problem is some computers can see eachother, some cannot, but nobody can message eachother at all.

The Computers we have are:

2010 MacBook Pro (Mavericks)

2007 Mac Mini (Lion)

Windows 7 PC

Windows 8 PC

Ubuntu 13.04 PC

Mine is the MacBook Pro, and I can see the Ubuntu user, but I cannt send a message, when I first send the message it looks as if the user is online and the message sent, but then a few minutes later the users name turns red and I get a message saying it couldnt be sent, the user may be offline. I get the same result when trying to message the Lion user, and I havent even tried either Windows user yet. The Ubuntu user cannot see or message anyone, and neither can the Lion User.

I should note that I do often print to a shared printer on the Windows 8 PC that is shared using Bonjour and that works just fine.

I dont know what to do, I was under the impression that Bonjour is one of thoes services thats supposed to "just work".

Our router is a Smoothwall Box, and uPnP is enabled, and Multicast is allowed.