This is a very old link but it's worth seeing: http://azureus.aelitis.com/wiki/index.php/Bad_ISPs

Try a connection & listening port somewhere between 49152 - 65535 such as 64049. If you're port forwarded then you'll need to do another port forwarding.

BTW is there any way to by-pass the router or is it a combined router-modem?

You said you were also unable to connect using BearShare. How about Phex? http://www.gnutellaforums.com/showthread.php?t=55271