The "push" method is one thing to try, but do this first:
1) Go to the Sharing tab of the comptuer you're trying to connect to and see what it gives for the "local subnet" address; it will look something like "EricNaus-Computer.local". Remember to look at the text below the box where you enter the Computer Name--it will probably be slightly different.
2) On the computer giving you the trouble, select "Connect to Server" from the "Go" menu. You should get a small dialogue box.
3) Type the address from step one ("EricNaus-Computer.local" or whatever) into that box, exactly as it appears on the other computer. Don't forget the .local, and remember that there's no punctuation after local
4) Click "Conenct". If the network is ok and everything is running properly, you'll get a login dialogue box. If that happsens, I have no idea what's up with the Network icon, but for the most part everything is fine.
If you get an error, there's either something amiss with your network, you typed in the computer's address wrong, or there's something wrong with the networking subsystem on that computer (which there indeed may be, given the misbehavior of the "Network" icon).