Unsure how old your devices are? That said, if you are connected via a WEP psk (pre-shared key), the security key can be recovered in just a few minutes using Open Source apps available in a freely downloadable distribution of Linux.
Verify the above and then adjust the BSSID (router) pre-shared key authentication to at least WPA/WPA2 if required, and also refrain from using any dictionary words or phone numbers for the key.
Now if that doesn't resolve the issue, perhaps your device would prefer to authenticate via a digital certificate. I don't feel you were experiencing this issue when any device is tethered to the phone. It sounds like the warning appears when the phone is 802.11 connected to a specific external router. Correct?
