I had serious performance Issues with my Magento CE 1.6.
Reason: Wrong and missing indexes. Magento fixed them is 1.6.2.
Here are the relevant DB changes. You might check if it helps you.
I reduced the checkout time for 38 lines with 73 items total from 123 sec to 4 sec !!!!
