Cannot connect to other mac shares

I have two macs on my network running the same version of SL (latest patch) and I have intermittent problems connecting to the shares on both macs. Firewall is off, file sharing is enabled, both AFP and SMB are selected, folders selected with read+write access. Occasionally the mac will pop up in finder and all works good but if both machines have recently been asleep it simply will not show up in Finder, or if I try manually connecting using AFP or even SMB all I get is "Connection failed, The sever xxxx may not exist or it is unavailable". Both machines are up and connected with valid IPs. Ocassionally the mac will appear in Finder under "Shared" but when I click on it, it disappears from Finder.

Any idea what could cause this? It's driving me crazy..