After some frustration with trying to get iTunes music sharing working between my iBook and my wife's Gateway Windows XP laptop, I discovered that Firewalk X 2 on my iBook was to blame.
I had already opened TCP port 3689 to all incoming traffic, but the Gateway still couldn't find me. Unlike Mac OS X's buiilt-in firewall, Firewalk X 2 requires the additional step of opening UDP port 5353 to incoming traffic, too. Essentially, I followed Apple's instructions for enabling iTunes music sharing on a Windows machine with a firewall. This resolved the problem and the two machines now easily share iTunes libraries.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20040131014143823