Кто провайдер? Связь - выделенка?
Вообще подавляющее большинство выделенок грешат пофигистским отношением к клиенту. Друг мой уже четырех провайдеров сменил. Первый раз у него проблема была именно с тем, что не открывался ни яндекс, ни рамблер, ни вообще большинство известных адресов. Работал без проблем только сайт районки (сайт провайдера). После проплаты выхода "на город" ему прописали другие DNS-ки, и вроде связь наладилась.
[offtop]Правда, он все равно от них ушел. Сейчас у него в квартире четыре провода, потому что каждый новый провайдер тянет свой 
[/offtop]