It could be some filepermission problems.
Run repair filepermissions in diskutility.
Remove folder ~/library/application support/kindle
Reboot again (dont know if this is necessary)
Go to Amazon website and manage your kindle
deregister your computer
Install Kindle from AppStore (not from Amazon)
Start kindle and register.
Go to Amazon again.
Select your items and action deliver to your computer.
Sync and wait for your items to download.
You've hit the nail on the head as far as downloading from the Application Store is concerned. The problem seems to be with the particular version of the Kindle app. The one from the Application Store is v 1.2.3. The one I had been using with Snow Leopard was v 1.5.1 which I downloaded from MacUpdate in April. It was great and I had no problems with it.
Being a later version it had a few more bells and whistles on it than 1.2.3 and I must admit I am missing a couple of them. I use a system of 4 bootable backup discs (don't beleive in Time Machine) and I actually sortred things out using one of them. Just for fun, once I'd done that I booted from another backup disc and just deleted/installed only the app itsef. Worked like a charm. I was able to register straight away and synchronise in the blink of an eye. Then I re-installed 1.5.1 and I was back to square one. Didn't matter of course, just cloned over the top of it, but I thought it was a useful thing to know.
Since my last post v1.6.2 has appeared in MacUpdate. Just for fun I installed it onto one of my backup discs to see what happened. It works okay. It has a couple of extra features that I like.
I did have to register again but that went through straight away. It is a bit iffy in that it flickers occasionally but basically it works as it should.