DNS sometimes works, but it is very slow.

network-manager is meant to manage your whole workstation's networking requirements in 12.04 along with resolvconf and dnsmasq-base.

dnsmasq-base is just the executable dnsmasq file which network-manager runs using a separate config and no start-up scripts.

resolvconf rewrites /etc/resolv.conf whenever one of the 12.04 integrated packages tells it via scripts that something has changed.

It doesn't sound like it's correctly installed if you don't have that dns=dnsmasq line in your config. It might also account for the slowness.

You could try dpkg-reconfigure on network-manager and on resolvconf

Alternatively if you are using programs like VPNs that are not integrated with network-manager or other non-compatible programs, you could de-install network-manager and resolvconf completely and rely on isc-dhcp-client to set up your network and DNS, or pppd if you're using a modem.

dnsmasq under control of network-manager is intended to speed up DNS look-ups through caching, but if you de-install network-manager, then you'll also get rid of dnsmasq - at least it won't run on its own. You need the regular dnsmasq package to get it starting up and running at boot time.

You don't say if you need DHCP or you have static IP addresses.

Remove /etc/resolv.conf and make a symbolic link as follows:

/etc/resolv.conf -> /var/run/resolvconf/interface/NetworkManager

That is, execute:

ln -s /var/run/resolvconf/interface/NetworkManager /etc/resolv.conf

Local DNS in Ubuntu is always a bad idea (resolving domains after 10-15 requests).