Olá @eduardok,
Explique pra gente: como sua rede está organizada?
Que tipo de firewall você usa?
Como você direciona o tráfego de sua rede para o Squid, por configuração no navegador, ou por proxy transparente?
E, last but not least, onde o Ubuntu entra em seu problema?