Mine connected to either of my routers on the first try. Does your give you an error or some unusual message? I do have my Telus 3200M gateway set to 2.4GHz wireless though.
Same as @Nighthawk, no problems connecting to any of 3 different Wi-Fi signals. Can you run a temporary Ethernet cable to the device and see what happens?
Are you setting it up using the remote, or an Android phone? I had problems using the automated process with the phone, and reset the device, and had success using the remote only.
WPS? I just typed in my password for the network. I disable WPS on all my routers. 🙂