I gave up reading on my kindle a while ago, because I could not get new books and I could not sync through WiFi, because the device just stopped seing my network.
Today, preparing for a small trip, I really wanted to make it work, so i started searching. This problem is pretty common amongst the kindle users, it seems.
The problem: The Kindle was designed in the USA and so uses only the US Wi-Fi channels 1 to 11. If your wireless router is set to use channels 12 or 13 (or is set to automatic) your Kindle won't see the network.
The answer: change your router setting to use channel 1-11 (I used channel 2, and my kindle connected instantly)!