I dunno if you figured out your problem yet, but in case you haven't, here you go... I was having the same exact problem, and I had installed/uninstalled Kindle for PC several times with no luck. It turns out that the firewall from firefox was keeping me from downloading Kindle for PC properly. So if you installed it using firefox, this might be your problem too. So I uninstalled it and installed it using Internet Explorer. I have no idea why this worked, but it is working fine for me now.
Hope this helps!
Thank you very much for this arienda05. I'm using a PC (Windows XP) and this "fix" worked for me. I'd tried downloading from Firefox and like many others uninstalled and reinstalled it a few times. I also needed to set proxy to "none".
Thanks