I encountered a Verizon Actiontec home wifi box that would connect for hard-wired, a laptop, and a tablet. It would not connect to a smartphone. The security was WEP. I changed the security to WPA2 and every device was able to consistently connect.
I encountered a CenturyLink Zytel PK5000Z wifi box that would not allow connections for transient devices. Devices that were consistently at the store were able to reliably connect. Transient devices would start to connect then fail to get IP address. There was no WEP/WPA security. Changing to WPA2 made no difference. Removing NAT made no difference. The firmware was up-to-date. I changed the DHCP expiry from one day to five minutes. This allowed all devices to consistently connect.