I'd also verify that the MAC address of the gateway is still in the ARP table as well, using 'arp -a'. ARP entries expire after 10 minutes.