When I use Limewire on a NATed internet connection, I usually don't have any uploads.
If I'm using it on a normal internet connection, my download requests to NATed hosts usually fail.

We really need the upload bandwith of all the NATed connections to keep gnutella alive.
Are you sure the push requests are working?

How did Morpheus solve the problem? I know people with NATed connections uploading a lot with Morpheus. Maybe the push request is routed only by the ultrapeere instead through the whole network.