Am running 4.1.1 on a GSM Galaxy Nexus and continue to have very poor connectivity issues with Wi-Fi (everywhere, not just in my house). Other than having an unlocked bootloader and being rooted, the device is stock.
My AP in the house is running on Channel 1, and there's no other WiFi that's close to my house. No RF interference to speak of (e.g. no microwave's running or 2.4ghz FH devices in vicinity). Right now I am not so close to the AP, but have good signal strength on my device: -65dBm. The AP is a Linksys WAP54g with the latest firmware available running WPA2 Personal AES. The device may eventually connect, but often it just hangs on "connecting." I've tried to change to WPA2 "mixed" (AES+TKIP) but that doesn't seem to have any impact (still hangs on negotiating). I would just chalk this up to a Linksys issue, but I have had same issues out in public Wi-Fi.
I was using Wi-Fi Analyzer to manage the connection, and didn't see the message regarding "Poor Internet Connection" and reason for failure. I changed the Advanced Wi-Fi option to deselect that option, and rebooted the device, and then connected OK.
I have a Nexus 7 on same network with no issues (the UI has no option for "Avoid Poor Internet").