Same problem here, 3GS very sluggish after upgrade. I am not using iCloud, all features turned off.
I have noticed the same battery drain referenced by others and the back of the iPhone is noticably hot -- and it now takes for ever to charge. Connect the dots and....as stated in another post, the CPU is running at high utilization level (downloaded sysstats lite and CPU utilization was over 90%). Funny, I had a similiar problem in Win7 trying to do the upgrade (should have followed my instincts) and had to track down how to stop AMDS from consuming 90% of my laptop CPU.
Anyway, as suggested in the other post, I disabled Notification Center and CPU utilization is down to a respectable ~6-10% when idle. The phone is now as resposnive as it was before the upgrade...but no notifications.
Ok Apple, seems like at least part of the problem has been identified, how about iOS5.01 please!!!