I had exactly the same problem with my Netgear WNDR3800 and tried the same things, with the same lack of success. As a last resort, I installed the open source DD-WRT firmware on the router. It's worked perfectly with Vestalink ever since. If you don't know about DD-WRT, here's the link:
http://www.dd-wrt.com