Since I upgraded my iPhone 3G (not 3GS) to Apple's iOS4 it has been running slow, and that is to put it mildly. It has been so slow I barely wanted to use  the damn phone! 

Reading a thread in the Apple Discussion Forums, I realised, like most things, when you simply upgrade software there is a bunch of detritus left behind, so following the post, I simply reset the phone through iTunes to factory settings, once done, I went and upgraded my carrier info (which it prompts you to do) and then restored it from the backup (that I made earlier) 

Voila, it is now running pretty snappily again. Joy!