Seems like 3.1.3 on an iPhone 3G is faster than on the iOS4.
Little trick mentioned on several sites is to turn off Spotlight on the iPhone.
You can disable it by going into: Settings -> General -> Home Button -> Search -> disable any functions you dont need/use.
