This is mainly for Google, as I found a lot of things talking about the error with not a lot of solutions when I looked for it.

I had a machine that was outputing the Neighbour table overflow message with reasonable frequency, and while it didn't actually seem to be causing problems it was disconcerting. Digging around seemed to suggest it was an ARP issue, with some pages mentioning Blaster - presumably because the scanning that this sort of worm can do is likely to fill up the ARP table?

Anyway, this machine has over a /22 of IPv4 space hanging off its various interfaces, so it seemed logical that I might need a larger cache than the default. I found this SuSE post which solves the problem perfectly. So I've added the appropriate magic to /etc/sysctl.conf: 

net/ipv4/neigh/default/gc_thresh1=1024
net/ipv4/neigh/default/gc_thresh2=2048
net/ipv4/neigh/default/gc_thresh3=4096

(Oh, and the message comes from net/ipv4/route.c in the kernel source tree.)