I recently also ran into dns trouble on ubuntu. I had to ditch the Cisco vpn client for the open source one. It wasn't playing nicely with ubuntu's recent changes with resolv.conf.