Hi,
There is this Apple Doc. http://support.apple.com/kb/HT3789
Basically some people used to turn Bonjour Off.
At OS X 10.6 Apple linked mDNS to the DNS service.
Then turning mDNS Off also turned Off DNS, which in turn means you can't access the Internet properly.
It obviously turns Off Bonjour as part of the process.
I would also check if your router is in fact allowing Local Traffic.
Although ports above 1024 are not open in router by default they can be open to local traffic.
Bonjour uses port 5353 to discover other Macs and Bonjour able devices.
(iChat/Messages also uses ports 5297 and 5298)
In the System Preferences > Security & Privacy > Firewall > Unlock the Pane and check Firewall Options
In here make sure it is not set to Block All Incoming connections.
Some outgoing connections may allow return data to arrive.
NOTE: I have not got a OS X 10.7 boot in front of me and the above are the Mountain Lion instructions.
Other then Snow Leopard using an Advanced button instead of the Options button I see little changes between those two versions.
8:12 PM Friday; February 1, 2013
Please, if posting Logs, do not post any Log info after the line "Binary Images for iChat"
iMac 2.5Ghz 5i 2011 (Mountain Lion 10.8.2)
G4/1GhzDual MDD (Leopard 10.5.8)
MacBookPro 2Gb (Snow Leopard 10.6.8)
Mac OS X (10.6.8),
Couple of iPhones and an iPad
"Limit the Logs to the Bits above Binary Images." No, Seriously