What OS version are you running? If it's pre-Tiger (10.3.x) you're probably in the same boat as me. See my post:
www.gnutellaforums.com/general-mac-osx-support/79967-still-can-t-connect-os-x-10-3-9-a.html
Otherwise it might be a port forwarding issue--see the third sticky thread in this area (Connection Problems) and look at the info in the first link there.