Сервер не может в исходящие соединения

Есть выделенный сервер на Debian 8. До перезагрузки все работало нормально. После перезагрузки все на первый взгляд работает, я могу подключиться по ssh, работают сайты и тд, но сервер не может установить никакое исходящее соединение никуда (Destination Host Unreachable, или No route to host, или Connection refused, или что-нибудь еще). Настройки интерфейсов не менялись, таблица маршрутизации выглядит легитимно, iptables пуст. Админы хостинга поковырялись и пока не смогли решить проблему. Какие у кого есть предположения, что могло сломаться, если считать, что gateway правильный?