You are not going to like the solution I found but...
After upgrading my mid 2010 13" MBP, 4GB to Lion, Safari was slow, mail was slow, booting was slow.
I tried everything I found here except adding more RAM; 32 bit mode for Safari, changing my browser to Chrome, resetting account permissions with terminal, running disk repair, etc. I even archived and deleted all my old email messages. All seemed to help a little bit, but the machine was still nearly unusable and would get worse by the week.
So I made sure I had a good back up and reformatted the disk and did a Time Machine restore. Still no joy.
One poster on this thread or a parallel one had mentioned the same thing and said his solution was to reformat and do a fresh install rather than a TM restore.
I said what the heck, if I'm going to reformat again I might as well drop a new drive in the machine. Put in the new drive and did a clean install from the App store. It has been 6 weeks now and the machine just screams - better performance than when it was running 10.6
Don't know if the drive replacement or the clean install was the trick, but as Disk Utility reported everything was good with the old drive I'll guess formatting and clean install would do it.
I also did a App Store Lion upgrade on a 2011 Mini - it has worked flawlessly without any issues.