I had the same problem (exact same message). The apple support article (http://support.apple.com/kb/TS2972) worked for me, i.e. make sure the firewall security setting (system preferences/security/firewall) on both your macs is set for "set access for specific services and applications."