Recently I upgraded my iPhone firmware to 3.1.3.  Immediately after the update, text messaging was SUPER SLOW and the phone was just plain laggy.  Opening apps would sometimes result in a white blank screen for seconds and all button presses lagged by 2-3 seconds.  I tried your standard soft-reboot (hold down SLEEP and slide to turn off), but that certainly didn’t fix it.

After posting a quick question on the Apple forums, the fix was easy:
http://discussions.apple.com/thread.jspa?threadID=2330402&tstart=0

Perform a HARD RESET by pressing HOME + SLEEP until you see the Apple logo.  Apparently this actually reloads OS X on the phone and it fixed my issue!