Ubuntu – DNS queries get routed to localhost on Ubuntu 9.04

For some reason, all DNS queries on one of my Ubuntu 9.04 boxes get routed to localhost, which results in no domain names being resolved. When trying for instance dig example.com, it hangs for ~20 seconds, before quitting with the message ";; connection timed out; no servers could be reached". However, dig example.com @193.75.75.75 returns the correct result immediately. This problem applies to all DNS queries, not only from dig.

$ cat /etc/resolv.conf
193.75.75.75
193.75.75.193

I do not have a .digrc, NetworkManager has been uninstalled, and the network is otherwise working (e.g. I can use it normally for hosts in /etc/resolv.conf). I do not have a local DNS server installed, and nmap confirms that nothing is listening on port 53. I have several other boxen running Ubuntu 9.04 on the same network, DNS is working fine on all of them.

I have used strace to confirm that dig actually reads resolv.conf:

open("/etc/resolv.conf", O_RDONLY|O_LARGEFILE) = 6
(...)
read(6, "193.75.75.75\n193.75.75.193\n"..., 4096) = 27

I have also used tcpdump to confirm that the problem is indeed DNS queries getting routed to localhost:

$ sudo tcpdump -i lo
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on lo, link-type EN10MB (Ethernet), capture size 96 bytes
14:11:54.175580 IP localhost.45910 > localhost.domain: 38233+ A? example.com. (29)
14:11:54.175633 IP localhost > localhost: ICMP localhost udp port domain unreachable, length 65
14:11:55.175542 IP6 ip6-localhost.54963 > ip6-localhost.domain: 38233+[|domain]
14:11:55.175575 IP6 ip6-localhost > ip6-localhost: ICMP6, destination unreachable[|icmp6]

I am out of ideas for resolving this issue, so any input and suggestions are most welcome.