I received my second kindle this week and I am getting the same problem.
I bought the kindle from amazon.com
I contacted amazon and they just point me to the typical instructions and if they don't work, they suggest me to call, but I live in Spain...
Any new ideas?