I'd just change the security code to something simple and try again or try the push button method.

I have seen this when the router is say set to 802.11n only and the device is 802.11g. Strange oversight on WiFi design that it can see the access point and fail like you wrote about.