As the questioner gives the contents of his /etc/network/interfaces I infer that he is using ifup to configure interfaces. But since he may actually be using NetworkManager, I will discuss that as well.
If you are using ifup then DNS settings go in /etc/network/interfaces. For each interface you add dns-* options appropriate for the nameserver(s) available over that interface. E.g., if a nameserver at address 1.2.3.4 is available over interface eth0, then add dns-nameservers 1.2.3.4 to the iface eth0 stanza.
If you are using NetworkManager then settings are entered in the Connection Editor (network indicator | Edit Connections...) in the IPv4 Settings tab.
Doing /etc/init.d/networking restart to reconfigure interfaces is deprecated. If you are using ifup then first ifdown each active network interface, then ifup each interface. If you are using NetworkManager then, first, disable networking using the indicator (top of the desktop); then open a terminal and run
sudo /etc/init.d/network-manager restart
and then enable networking using the indicator.
Or you can just reboot.
Regarding the fact that /etc/init.d/networking restart resulted in
RTNETLINK answers: File exists
Failed to bring up eth0
This means that ifupdown thinks that eth0 is already up. Use ifdown --force eth0 to cause ifupdown to stop believing that it has already configured the interface.
Regarding the "deprecated" message, this message is no longer printed in Ubuntu 12.10 but you should still note that initscripts are "on their way out". To restart a service foo, use service foo restart or restart foo. Note also that if you want to reconfigure your interfaces it is better to ifdown them one by one than to rely on restarting "networking".