Thanks for starting this topic friend. Even I have a similar issue with my Kindle. I recently replaced Wired router and got a new Westell DSL Wireless Gateway from ATT. Now all the other device except the kindle is working fine with this router except the kindle. I have put the same network key that I have put for the other device but still it is not working.
When i tried to contact the Amazon guys for the help on this issue I was told that all the software was up to date on the kindle. So the issue is related to the router setting . And when i contacted AT&T, they said that the problem is with Kindle as all other device working properly with the router. I donít know what to do. Its been a week now.