Any firewall software installed? Bonjour runs on a different port than the shares themselves, so maybe the Bonjour port (detection) is allowed, at least in one direction, but the daap port (3689) not? I remember there were some complaints about the McAfee firewall around, use the search function here if you have that running.
And I guess you checked the option in iTunes to not only share, but also look for shares? 😉