To elaborate on Franky's answer, this is quite likely a problem with the configuration of /etc/nsswitch.conf.
tl;dr: Change the line
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4 in /etc/nsswitch.conf to
hosts: files dns
There is a line in /etc/nsswitch.conf named "hosts:" that determines how your computer will resolve hostnames into IP addresses. (Read more about this process here: https://help.ubuntu.com/10.04/serverguide/network-configuration.html) This line is where the problem most likely is.
By default Ubuntu first checks the host file to see if the hostname has been manually specified there, and then it runs a minimal Multicast DNS query (this is used in zeroconf environments, Wikipedia has an article on it here https://en.wikipedia.org/wiki/Multicast_DNS if you want to learn more), followed by a regular dns query, and then finally a full Multicast DNS query.
In corporate environments that don't have reverse DNS set up properly (which apparently is often the case) the Multicast DNS queries cause major slowdowns. To fix the problem you should either fix reverse DNS or remove the Multicast DNS queries from the configuration. Given that in a corporate environment you likely have a DNS server of your own, I'd recommend just getting rid of the Multicast DNS query option from the configuration.
See https://bugs.launchpad.net/ubuntu/+source/nss-mdns/+bug/94940 for more information about this problem.