Ese problema es característico de las redes que salen a través de squid, con los puertos especificados en IExplorer.
Por eso squid NO es bueno para compartir la conexión a internet. Supongo que se les ocurrió eso porque hacen algo similar con algún soft en windows, que dice ser un proxy pero que, además de hacer nat, es un proxy socks.
Squid no es un proxy sock.
Para compartir la conexión, usen iptables. Y en el explorer dejen todas las opciones por defecto. Ni se les ocurra tocar un puerto si quieren que irc y mensajería anden bien.
Acá tenés una explicación de cómo hacerlo:
http://www.espaciolinux.com/postt4750.html
Si quieren usar squid (muy, muy útil debido al cache de páginas, que acelera bastante la navegación), configúrenlo como proxy transparente.
Saludos.