No i działa. Ustawiłem same OpenDNS-y tak jak radziłeś fnmirk. Dziwi mnie tylko to, że na innym wirtualnych maszynach mam cztery dnsy wpisane i działało, a tylko na debianie miało z tym problem.

Mam podobny, problem. Z tym, że mój Debian jest na virtualboksie.
Mam stworzonych kilka wirtualnych maszyn z innymi Linuksami (m.in Ubuntu) i na nich aptitude działa bez problemu. W czym może leżeć problem?
Moje dns-y:

nameserver 195.114.161.61
nameserver 195.114.181.130
nameserver 208.67.222.222 ...