Apparently the combination of a WLAN router that blocks IPv6 DNS queries of type AAAA (in my case, it was a Siemens S1621-Z220-A sold as Alice Modem 1121 WLAN) and the current version of Google Earth for Linux (I am using 5.1.3533.1731 from Medibuntu) do not work well together. The problem is that the router simply throws away AAAA queries (or generally, any type it does not know), so the DNS query times out. However, Google Earth does not seem to fall back to IPv4 queries (type A) in this case, and shows a message about network connectivity errors. I don’t know if it’s Google Earth’s fault or if the underlying eglibc resolver of my Linux system does something wrong, anyhow there is a fairly well-commented bug report on Launchpad for Ubuntu Karmic and Lucid which explains the issue.

Anyway, I got rid of the problem by manually configuring a nameserver on my local machine (for example the nameserver(s) of your internet provider, or the ones of OpenDNS), and not using the WLAN router as a resolver. NetworkManager allows you to do this by editing a connection and choosing “Automatic DHCP (Addresses only)” on the IPv4 register tab; or you can write the settings directly to your /etc/resolv.conf (here for the OpenDNS servers):

nameserver 208.67.222.222
nameserver 208.67.220.220