Eu descobri a resposta. O problema é que a Verizon cortará uma conexão se receber 10 pacotes inválidos em um intervalo de 2 minutos. O problema é que eu não estava usando pacotes NATing corretamente, pois também estava usando isso como um roteador. Os pacotes enviados da lan em ponte estavam sendo enviados para a verizon com um IP de origem de 192.168.123.XXX. A Verizon (com razão) decidiu que esses pacotes eram inválidos e desligariam a conexão. A solução foi simplesmente adicionar essa regra do Iptables:
iptables -t nat -A POSTROUTING -o ppp0 -j MASQUERADE