That's a known issue between makes of wifi equipment. I have no cure for you if latest firmware and drivers don't fix it other than to replace the hardware.
For now, to get some security, use MAC FILTERING until you find the bad item.
I setup my home network. Strong connections with security disabled, then when I enabled WEP encryption I received the message: "You Are Connected to the Access Point, but the Internet Cannot Be Found." When I disbled security, I connected to the Internet with no problem.
I connect to Cox High Speed Internet through a Motorola 5100B modem, hardwired to a Linksys WRT 54GS wireless router, then wireless to a Linksys Wireless G USB Adapter plugged into a Sony Vaio running Windows XP. I can't connect to the Internet when WEP is enabled although I show a strong wireless connection (90%+ signal strength).
I rechecked my SSID and passkey settings and still it didn't connect. I tried repairing this through one of the tools on my XP. No luck. I then contacted Linksys tech support who ran me through resetting the modem, downloading new firmware, and temporarily disabling my Firewall, but to no avail. The Linksys tech asked me to test the system using a wireless laptop. I borrowed one from my neighbor, inputted our passkey, but although I could get into the wireless network again I could not connect to the Internet. They then told me to exchange my router and USB adapter. I exchanged the equipment, ran the same tests, went through the same drills with the techs, and the same problems resulted. I called Cox Cable for their help and they said it was "not our problem, contact Linksys." Aargh!
Two last points: When I ran a scan of the system I receceived messages that my DHCP Server had an invalid address and that the IP Address failed because the system was not able to renew the IP Address.