I started having the same problem at about 8am est. are you on godaddy by any chance? I just went through all my sql tables, analyzing and repairing them, optimizing etc. I did install the wp-cache that only made thing worse. It seems more server side, in the sql tables than anything…very odd.
Had a problem like this last week, before the upgrade, godaddy couldn’t make anything out of the sql errors i was getting, but next thing you know, all was fine again…grrrr, i’m super frustrated.