>Ошибок у меня в логах нет, но точно такие же симптомы.
>Верчение настроек пока ничего не дало.

Со скоростью я разобрался. Дело было таки в ДНС, т.е. ДНС то нормально возвращал запросы, но сквиду чет не нравилось пока в его конфиге в строке dns_nameservers не прописал первым ДНС-сервер провайдера. Потом убил и заново создал кэш и скорость появилась. Странно, что в той же сетке работает FreeBSD7.0 и сквид Version 3.0.STABLE10 , и ему строка dns_nameservers ненужна, он всё прекрасно подтягивает из resolv.conf
НО !!!, ошибки в логах не пропали