Отпишусь, в чем была проблема.
Было две сети 
192.168.219.0/24 и 
192.168.218.0/24, и шлюз объединяющей эти две сети. Данная схема показана на картинке:
                 +-----------------+                  +------------------+
                 |192.168.218.128->|------------------|<-192.168.218.129 |
-----------------|<-192.168.219.1  | 192.168.218.0/24 |                ->|----//----
192.168.219.0/24 +-----------------+                  +------------------+ Internet
Проблема заключалась в следующем, машина из сети 
192.168.219.0/24 посылает пакет на машину находящуюся в сети 
192.168.218.0/24. Так как она ничего не знает про сеть 
192.168.218.0/24 она отправляет данный пакет на свой шлюз по умолчанию 
192.168.219.1. Шлюз, передает пакет через свой интерфейс с адресом 
192.168.218.128 в сеть 
192.168.218.0/24. Машина из сети 
192.168.218.0/24 получает адресованный ей пакет. А так как она ничего не знает о сети 
192.168.219.0/24, свой ответ она отправляет на свой шлюз по умолчанию 
192.168.218.129 и таким образом, ответные пакеты уходят совсем не туда куда надо.
Проблема решилась добавлением маршрута в сеть 
192.168.219.0/24 на всех машинах, находящихся в сети 
192.168.218.0/24. То есть:
route add -net 192.168.219.0/24 gw 192.168.218.128