So, it's been quite a while since I started having problems with accessing google.com and other Google sites from my home laptop, running Kubuntu 9.04. A WinXP station connected via the same router had no problem whatsoever. Finally I've had enough of it, and I had a look at the typical failed connection with Wireshark. And, sure enough, what I saw is that timestamp TCP option is being used (or misused, so it seems). I turned it off - and everything works just fine since then.