А поробуйте всетаки обойтись без сквида. Только ради ввода пароля-городить сущности... Хотя-не нужно прописывать параметры прокси у юзеров (типа все прозрачно)....
"Эксперементните":
1.Отключите редирект на сквид.
2. Убедитесь что поднят NAT -( как описано выше)
3. Проверьте, что авторизация проходит и что после авторизации машины вся подсеть начинает ходить в инет.
4. Попробуйте авторизоваться с помощью команды вида:
wget --post-data 'user=login&password=passw' http://example.org/auth.php
Где вместо login/passw - ваши соответственно, а закачиваемая страничка, например http://ya.ru/index.html (любая существующая с любого сайта). Если после такой авторизации инет заработал- оформляем это в файл скрипта и запихиваем в crontab на сервере с переодичностью достаточной для "поддержания" соединения.... (Незнакомые термины ....wget, cron - смотрим в вики...)