So it seems Ubuntu 12.04 uses a local DNS server for all connections, regardless what you specify in Network Manager.
The easiest way to fix this is edit the following file:
sudo vi /etc/NetworkManager/NetworkManager.conf
Remove the dnsmasq line, save, and reboot! Your settings will now be fetched from DHCP or taken manually from Network Manager again!