Após algumas verificações adicionais, ficou claro que o firewall do iptables estava bloqueando as conexões dos hosts. Adicione regras para permitir o tráfego SQUID de acordo com documentos do RedHat: link
As regras em si devem ter esta aparência:
-A INPUT -s <your.internal.network>/<netmask> -p tcp -m tcp --dport 3128 -j ACCEPT
-A OUTPUT -d <your.internal.network>/<netmask> -p tcp -m tcp --sport 3128 -j ACCEPT
A última regra é necessária apenas se o tráfego de saída também for filtrado (não tenho uma caixa RHEL para verificar a configuração padrão). Definir o acesso apenas da sua rede interna também é muito importante para a segurança. Ou você pode configurar o seu squid para ouvir apenas na interface
http_port your.internal.ip.address:3128