First off, make sure you're using the sun jre - Gentoo defaults to blackdown and we've had problems with that a lot.

In the 4.1 series (to be released as 4.2 tomorrow) we have improved the initial connection logic greatly. I recommend either getting the latest beta (which is nothing other than 4.2 itself), or copying the ~/.limewire/gnutella.net from a box where limewire connects fine over yours. That file contains the entry points to the network that specific node knows about - it should let you connect no slower than the node you copied it from.

Hope this helps - let us know how it goes.