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 22.214.171.124 is available over interface eth0, then add
dns-nameservers 126.96.36.199 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.
/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 restart network-manager
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
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".