When you used the recovery menu what did you do?
This may help...
http://www.mobileread.mobi/forums/sh...d.php?t=113362
If it were my Kindle I would try formatting it using FAT32. If you have Windows 7 I would use a 3rd party app to format it. I've had some problems with the way Win 7 formats FAT32. Then go into the recovery menu and then initialize the partition.
Do this are your own risk, but since it already doesnt work what do you really have to lose?