Long delay connecting to shared Macs

Just started to have a weird problem. This occurs on 4 Lion Macs in my household, not on 2 other Lion macs, and not on 2 Mountain Lion Macs. Which makes it even more frustrating...

When I click on a Mac under Shared in Finder, it takes at least 5 minutes for it to connect. If, during this wait, I click on Connect As, I can immediately connect, either as Guest or a registered user. Screen Sharing has a similar very long wait. I've tried to isolate any software that is different between the machines, with no luck.

Anyone have any ideas?