Based on the error message alone it looks like your server is being blocked in some way, potentially a firewall, but I know by default OS X doesn't turn on the firewall... Check in System Preferences -> Security & Privacy -> Firewall (tab) ... and make sure it's disabled.
Other than that, when you try to connect, do you see any information in the server console? What does your network look like? Are you trying to connect locally (localhost, 127.0.0.1, ::1, same computer), on the same subnet (in the same house, on the same wifi/router), or externally (over the internet)?
Are the clients running macs as well? Are you using any non-default configurations? Lol, we need a lot more specific information in order to help.