Go through the info in this sticky
http://www.gnutellaforums.com/showthread.php?t=61028
What version of FW are you using? There was a problem with connections in the older versions but an update to 4.13.1 has fixed that particular problem.
http://www.frostwire.com/
If there's no problem with a software firewall, your modem/router probably has it's own internal firewall, that might be what FW's detecting. The sticky link has heaps of info about this.