After trying everything (restart processes, taking caches off, etc.), I asked our ISP to look and he found that one of the DNS entries listed in resolv.conf was offline.
Just posting this to add to the knowledge base since I didn't find a similar problem in a search here.
"It was a DNS issues. One of the DNS servers listed in /etc/resolv.conf was offline, for some reason, this was slowing down your site."