Same problem. Original iPad 64GB, iOS 5.01 has turned it into a sluggish piece of hardware. So much so I'd rather go back to using my netbook. Tapping on apps sometimes takes 3-5 seconds to open, the keyboard frequently doesn't immediately respond, and typing is frequently interrupted by pauses. I find that I have to shut down/restart the iPad to get performance to return to something "normal" often.
Turning off notifications helped, but it's still much slower than iOS 4.x.
Turning off notifications helped, but it's still much slower than iOS 4.x.