Mhm... this rings a bell. In the first 2-3 days, I had my router (11b, not 11g) set up with WEP128 until I found out that somebody had played with my firewall settings; this made me switch to WPA. But: I can't remember any connectivity problems in those early "WEP-days", even though I played around with my Nokia 770 more often than I do now. I'll try to confirm that this is a WPA-only problem here when I'm back home.

EDIT: I'm home now an yes, it is a WPA-PSK-only problem. WEP works without any troubles. Thank you, jaycee, for clarifying this detail. It doesn't really help, though, because I'd like to keep WPA on the router.

BTW: "Connect"/"Disconnect"/"Connect" on my 770 does not solve the problem here. That's what I did all the time before I found out I had to reset my router, not the 770.