The solution for us was to set this in sysctl.conf:
net.ipv4.neigh.default.gc_thresh1=0
https://bugs.launchpad.net/ubuntu/+source/linux/+bug/1331150... https://bugs.launchpad.net/ubuntu/+source/linux/+bug/1331150...