I'm guessing UPnP worked for you previously? Whilst you might have been able to connect with LW 4.12, from memory it did not have a firewall indicator that something was not quite right. Just curious about the combination of airport & router. BTW why use the Gateway if you have the airport?

At least I presume you have LW set as an exception in OSX's firewall, or is it turned off? OSX Firewall settings for Tiger/Leopard

You should make sure you have a fresh gnutella.net file; see 2/3 way down this page: If LW 4 Will Not Connect (click on the blue link)

You could also check this method of excepting LW through your Gateway: Port Forwarding for the 2 Wire 2701HG-G

Since you are set to using UPnP for your airport (which will cause LW to use different ports each time connected), perhaps you should set a wide range of ports for LW to use via the Gateway. eg: 2000 - 65535. And do one rule for each of TCP & one for UDP, or both together if possible.