Auch auf die Gefahr, daß schon alles gesagt wurde - ich kann mich nur all jenen anschließen, die zu einer kompletten Wiederherstellung über iTunes (aus dem iPhone Wartungsmodus) raten.
Habe ein stinknormales 3G (16 GB, kein JB) und gerade eine 75minütige Telefon-Session mit einem AppleCare-Berater hinter mir. Den wollte ich eigentlich nur fragen, wie ich auf 3.1.3 zurückgehen könnte, damit das Ding wieder vernünftig läuft. Aber er hat mir dermaßen glaubwürdig versichert, nach der Wiederherstellung wäre alles wieder perfekt, daß ich ihm geglaubt und die Aktion mitgemacht habe. (Netterweise hat er die ganze Prozedur Stück für Stück mit mir durchexerziert.)
Ergebnis: Das gute Stück rennt jetzt mit iOS 4.0.1 wie die Feuerwehr (würde sogar sagen schneller als mit 3.1.3) - und das, obwohl ich alles aus dem letzten Backup zurückgespielt habe, weil sonst alle SMS und viele andere Sachen flöten gegangen wären.
Wer also von der neuen Langsamkeit genauso angefressen ist wie ich es war, sollte diesen Schritt in Erwägung ziehen. Ich für meinen Teil kann nur sagen, daß es sich mehr als gelohnt hat.
Viel Glück!