I had some time available yesterday so I wiped my iPhone before plugging it into iTunes and selecting "Set up as a new iPhone" option. It now appears to behave like new even with everything re-sync'd (albeit settings, game save positions/scores and text messages lost).
Ever since I upgraded my iPhone 3GS to OS 3.1, it behaved rather sluggish (even with the latest 3.1.2 installed). Wipping my finger across the screen to unlock the phone sometimes required various attempts before the GUI actually responded and the phone unlocked, writing on the keyboard was commonly delayed and I found I just had to type "blindly" for a few seconds before the keyboard responded and the text actually hit the screen. It was as if there was some resource-intensive background operations that the iPhone was carrying out every so often, and if I actually wanted to use the phone during this time, I had to endure sluggish operation until it completed (about 3-4 seconds later).
I thought the phone was at fault until I lost it and then with a brand-new replacement 3GS, using the "Restore from the backup of" option in iTunes, the behaviour was exactly the same.
So yesterday I used the Erase All Content and Settings option from the phone before plugging it back into iTunes and selecting the option Set up as a new iPhone. It now works perfectly again!