In my experience, the most helpful are:
Wipe Davlik Cache
I only formatted my SD card when I starting using Honeycomb ROM's, and then I had to also use the NV flash to reset my system partition as well (250MB). I've never needed to fix permissions myself, but I know some problems require you to do so.
There is a market fix you can try, listed here:
Working Market fix (tested on TnT Lite, should work elsewhere) - xda-developers