Mine was slow very annoyingly slow to the point where it doesnt want to do anything at all.OS4 is no good for the 3G at all in my opinion.I have tried all the things mentioned to no avail,so i have downgraded to 3.1.3 again and its back to its normal happy self.
This process worked for me too.http://findtut.com/easy-steps-to-downgrade-from-ios-4-to-ios-3-1-3-536547
Follow all the steps in this link guys it works perfectly. Definitely recommend it.
Mine is still slow and buggy; I must have reset it 20 times still with no improvement.JUST DO A HARD RESET!!!!
do it twice.. or even more.
I had to do it 3 times.