Failed network lookup

I'm running Kubuntu 12.10. I am having three networking problems that I think might actually have a common cause, even though they are in apparently unrelated areas. I had them in 12.04 also:

1. When viewing a number of different videos -- but not YouTube -- I get the message VE_FMS_CONNECT_FAILED, which says that the video is not currently available.

2. The launchpad-getkeys program isn't able to find the keys because it can't do the nslookup for the keyserver URL (and which URL it is doesn't matter). If I use the -k option with the IP address of the keyserver, however, it works.

3. The program youtube-dl gives url-open errors with this command:

   youtube-dl http://www.youtube.com/watch?v=EqGRROao5-M

However, if I precede the command with http_proxy like this:

http_proxy="72.64.146.135:8080"  youtube-dl http://www.youtube.com/watch?v=EqGRROao5-M

it works. (I know nothing about that IP address; I just copied it from a posted example.)

Two common elements of these examples are:

1. They only strike a few users, not all.

2. They all involve the failure of some network lookup.

Two causes that have been suggested are (a) firewall interception, or (b) proxy misconfiguration. However, ufw tells me that the firewall is inactive, and Network Settings / Proxy tells me that there's no proxy.

I was trying to come up with a more informative title for this thread, but wasn't able to.