I just replaced a Belkin Pre-n router with a Belkin N1. My N800 was connected to the internet just fine with the Pre-N and I had a hell of a time getting it to see the network, and then connect to the network. It turned out that my WPA-pre-shared key was either too long or had symbols in it that weren't read by the router, I guess, because when I removed the symbols and went with all letters and numbers it finally connected automatically. What tipped me off to this was a window that said, "Authentication failed." Try looking at and altering your security entries.

EDIT: I meant I had a hard time connecting with the N1.