I was having the same problem, and it looks like it could be due to having Development enabled on the device.
On the Apple Dev Forums I posted to ask about this for my problems (my post) and someone rightly reminded me that a lot of developers have been complaining about sluggish development devices.
So I went to the Organizer and Ignored my device from there, removing it as development enabled. I restarted the device and sure enough my MKMapView was a lot snappier. It was still sluggish at times, but the performance improved significantly.
Try it out for your device and see if you notice a difference.
