iktus,
Проверь, чтобы на гейт-машине в настройках стены не был выставлен режим "стелс" (в окне Internet zone security переставь уровень на medium). Должно заработать.
А стенку на тех машинах, которые ходят через гейт - все таки отдельно не мешает поставить. ИМХО, разумеется.