I've had Netgear router and had intermittent wireless connection issue. I've replaced that with lastest Wireless-N router (WRT-310N) from Linksys. All devices are connecting via Wireless-G mode. I'm having the same issue. My laptop do not see the router until several minutes. What could be causing that?
Do you have multiple wireless clients connecting? Have you checked the channel that your router is broadcasting on? Sometimes there can be interference, as wireless B/G use the same band as wireless phones.
your laptop is 'old-ish' and cannot connect at the 'n' speed so it has to negociate with the router what speed they are both happy with. and this may take a 10s of seconds. also you coudl have neighbours on the same channel or SSID