Weird, do you have any non standard characters in WIFI name or password (like !*/$#\ " ) ? (though this should be fine (had to put a lot of code to handle this)).
The only other thing I can think of that will cause this is if your WiFi router is set to 5 GHz?
Try change it to 2.4 GHz, or if your router supports it add a guest 2.4 GHz network.
Edit: the obvious cause is typo in SSID or password, but I assume if you tried for that long you have it correct.
Edit2: It also expects the router to assign IP via DHCP. If you turned DHCP off turn it back on or try get to the devices MAC address when you connect with phone and map MAC to IP in router (fixed host).
Edit3: same train of thought, if you have mac address filtering turned on in the modem, your modem will block the device.
Edit4: perhaps try closer to WiFi router, I have never had any range issues but my place is smallish.
Note: Before that Connection Fail message it has tried to connect 20 times, so its not for lack of trying