I had this exact problem with my dlink router. It took them about 3 firmware upgrades to get it fixed. If i used any p2p software the router would say connected but not one computer could connect to the internet. I actually ended RMAing my router and the replacement did the same until they brought out new firmware. Hofefully linksys will do the same.
My friend also has this problem with a netger router, and he still hasnt got it fixed. Maybe its an England compatability thing?
If I were to buy a router now I would probably go with USR, they seem the best
IMO.