Клёвый Админ

Не хватает информации, покажите пинг 8.8.8.8 и трасировку до него же.
Покажите настройки файрвола в керио.
Не очень понятна фраза "При этом на сервере интернет есть" это что значит? На каком сервере?

Важно понять, у вас проблема в ДНС или в сети. Если первое - пинги будут ходить, трасировка будет работать, если второне - нет. Ну и потом уже исправлять то что нужно.

Если есть доступ к настройкам керио - задача видится решаемой, иначе будут трудности.

Итак, в первую очередь. Шлюз и прокси сервер связанны очень слабо. Если прокси сервер находится в той же сети, что и целевой компьютер, то шлюз на сетевой карте целевого ПК может быть не указан вовсе, для обработки трафика используется именно проксирование, а до самой прокси трафф будет идти напрямую. Если же прокси в другой сети, то для достижения её - трафик будет идти через маршрутизатор этой сети (сети прокси, это не обязательно будет основной шлюз - шлюз по-умолчанию).

Теперь в твоём случае. Пинг не идёт - проверяем настройки шлюза, сети, файрвола.
Прокси не пропускает трафик - проверяем настройки файрвола, настройки сети.

Вообще ситуация странная и методы диагностики не те. В логах вообще один сплошной UPnP (читать как "не требующие настройки соединения"). Очень похоже, что DHCP поехал по пи*де или адресация сбилась.

Нужно:
1. telnet на адрес прокси, на порт прокси, должен быть ответ.
2. Пинг на адрес прокси, должен быть ответ
3. Пинг до DNS, должен быть ответ
4. nslookup до ДНС сверера, долже быть ответ.

Может, просто в файрволе что-то ткнули, или правила местами поменяли.

А давай я напишу не так как будто ты хочешь что-то не укладывающееся в твой трудовой договор, а как будто бы ты админ этого самого Керио и тебя хотят обойти =)
<параноя_mod>
Разрешаем только HTTP + HTTPS
Включаем прозрачный и не прозрачный прокси + принудительная NTLM авторизацию + Привязка к домену
На самом деле ещё лучше всего поднять прокси на SQUID сделать его родительским и дополнительно прогонять трафик через него и его ACL и правила фильтрации.
Делаем скрипт автовхода, плюс групповыми политиками тюним браузеры на использвоние NTLM
Поднимаем свой CA и генерируем сертификаты для HTTPS авторизации через веб форму
Включаем статистику трафика и хранение её
Блокируем ДНС запросы куда-то кроме твоего сервера
Блокируем VPN и доступ к прокси
Включаем защиту от MAC-спуфинга (плюс всех неугодных блокируем по mac, точнее разблокируем только известные mac)
На каждое подходящее правило навешиваем веб инспектор и планировщик доступа (например, после 8-ми закрываем клюшку)
Создаём QoS правила и блокировку P2P
Включаем (ломаем) веб фильтр и блокируем доступ к Порно, Наркотикам, Поискам работы, VPN серверам, Анонимным прокси и куче ещё всего
Включаем антивирус и блокируем скачивание zip, rar, exe и кучи ещё всего
Включаем защиту от угадывания пароля и блокируем таких пользователей

Делаем исключающее правило для себя. Включаем контру, ставим на закачку порнушку свежий дистрибутив Fedor'ы в торренте.

***
Как такое обойти? Подключится через HTTPS VPN или, возможно, найти что-то вроде HTTP Tor Browser. Либо уже ломать сеть, а не файрвол.

***
Как обойти ваш Керио?
Скачать с toonel.net лёгкий java прокси или работать в режиме Turbo в Опере или Я.Какбы.Браузере.