We sometimes get problems like this with customers who call us at work, but I stress that just because someone has similar symptoms it doesn't means it's the same fault... so this is just some thoughts
What I usually do (hoping that the customer is going to be able to set their router up again) is hold the reset for 15 seconds and let the router reboot itself. That should put it back to its out-of-box settings.
Then, get them to scan with their laptop.
If it turns out the laptop is using the non-Windows wireless software I switch back to Windows wireless zero configuration and rescan. Usually the machine then finds the router.
Next step is to try and connect. Annoyingly, router vendors have started supplying them with security already enabled and that can be a problem because a customer will swear they typed the key in right when in plain English they didn't get it anywhere near right, so make triple-sure you do put it in properly when you get to that bit
(Note: had a customer the other night with whom I was doing a walkthrough of recovery. Three times she told me everything was unplugged from the back except for the keyboard, mouse, monitor, and power cord. To start with, what she actually meant was that she had unplugged nothing. 2nd time, she had unplugged the printer. Third time I discovered she had still got the ethernet cable and dialup modem connected along with a box she didn't know about :rolleyes: ).
You've already done full recovery on your laptop from what you said - that would be another thing we'd then try.
If another machine can connect to the router (by cable, for example), we'd also try disabling security while we tested it just in case. I have definitely had several cases where security was the issue somehow.
Ideally, we'd then get the customer to take the laptop to a store and test it on the store network (we support machines bought in a large computer chain). Maybe ditto the router.
Once you have enough evidence for which one it is, we'd either repair the laptop or send them back to the store to get the router replaced.
The thing is, if both machines are in default state and working properly, there should be no problem. So it is simply a case of finding out which one has the problem, and then if it is s settings issue or worse.