Have you restarted etc? It always seems to take a long time or restart for newly shared computers to show up for me.
Then, if indeed windows sharing and file sharing is on and you're on the same network/workgroup etc, then the name of the computer will show up in my network places and windows shares will show up in network under the name of the computer (you still have to mount network shares in tiger which is a big of a pain).
You could always try pinging the other box to be sure they're seeing each other at all.