I have an odd problem with my WGR624 from Netgear. I can't connect to : secure.skype.com, www.metro.se, www.tv4.se, www.kanalnio.se and my ISP´s smtp server. The problem only occurs when I connect to Internet via my router, if I hook up my computer directly to my switch (cable modem - switch - router) it works just fine. I have tried disabling all my security programs, but it still doesn´t work. I have tested my router with at least three different laptops - same problem.
You seem to have your answer with the router. Try reseting the router and building the security from scratch. I had a issue with a website not being able to access a few days ago and I traced the route to the router and looked at the traffic coming and going through the router and it kept dropping the packet on me so I rebuilt from scratch and that solved it.