Please pay attention to this recommendation. You will DEFINITELY see a speed increase if you "reset all settings". Do NOT "erase all content and settings" however or everything will be erased from your phone.
Resetting the settings will make things MUCH snappier and you really don't lose much. I had to go back and change a few phone settings afterward, but all of my mail accounts, contacts, calendars, notes, music, applications, etc were still there. My applications were re-ordered in alphabetical order though if I recall correctly. Not a huge deal though. My 3.01 3G iPhone was much more responsive afterward. Highly recommended if your phone is running slow.
That's brilliant!
However, I wonder how long I'll go before speed begins to deteriorate again