I'm having the same issue with my Kindle 2 now. Me thinks there is something rotten in the state of Amazonia.
Doesn't seem to be a problem with the 3G since I'm able to buy new books through the Kindle, I just can't get them down to the Kindle. It was able to accept an email address change to the Kindle settings...
Humm