The "No gateway reply" is one of the problems I've been struggling a long time with. While people have posted several tricks to solved it, none of them worked (at least not for me), and in addition my Nokia 5800 worked on other people their WIFI without a single problem.

Based on that, everything pointed to my WIFI router (a Linksys WRT54GR BTW), but on the other hand I've various WIFI devices that work without any problem on my WIFI router (so that points again to the Nokia as being the guilty one).

A couple of weeks ago, someone told me the same problem (but I guess it was with a 5530) and surprise... he also had a WRT54GR. Therefore I checked once more the Linksys support site, and yes... there was a new firmware (1.1. After I installed this version... all problems with the "No gateway reply" seems to have been solved... fingers crossed.