Go into the router's Wireless settings... for starters, see if you can use WPA instead of WEP; WEP has always had problems. That right there might be your problem.
Next, see what Channel the router is broadcasting on. Default is 6. I just put a new router in today and had set it to 8, and my Wii and PS3 would NOT talk to it at all. Changed it back to 6, and all is fine.