Amazon's K4Mac troubleshooting page is here:
http://www.amazon.com/gp/help/custom...deId=200443870
However it does not seem to address the problem you are seeing.
First of all: it should work. I'm running 10.6.7, and K4Mac works just fine.
I am guessing that your uninstall consisted of dragging Kindle.app to the Trash. This would leave pre-existing Preferences and cache files intact, which might cause problems when you reinstall.
So what I would try in addition is to delete the K4Mac preferences and user data, empty the Trash, then reinstall.
The preferences file is at this location:
/{your system drive name}/Library/Preferences/com.amazon.Kindle.plist
(you might also see another one from an earlier version of K4Mac:
/{your system drive name}/Library/Preferences/com.amazon.KindleForMac.plist)
The user data/cache is here:
/Users/{your user name}/Library/Kindle
You can leave the content in Documents/My Kindle Content there, at least if the above solves the issue.
Make sure you have the latest version ready to install, and then install. You'll need to re-register the app to your Amazon account, but hopefully everything will work after that.
If any of the above makes you nervous, call Amazon CS and let them walk you through everything. They may know of a quicker way to restore K4Mac to health.