Problem finally fixed! This has been annoying the hell out of me for weeks.
It turns out the problem was with my
file, which had the following entry
hosts: files wins dns
and I changed it to
hosts: files dns
That is, Ubuntu was trying to resolve hostnames using a WINS server before trying DNS. I don't even have a WINS server, so obviously this causing massive delays in resolving any name, making web browsing interminable.