Matthew Yohe
macrumors 68020
Most people I talked to had problems when upgrading to iOS4 on a 3G. Try doing a restore and starting fresh with iOS4 (no backup restores).
Some people say starting fresh is a pain, but I started fresh on my iPhone4 and it took maybe an hour or 2 to get everything to where I wanted in terms of settings. I lost text messages and game saves, but do you really need all of those?
Yeah, this is exactly the problem. For some reason the transition from 3.0 to 4.0 on a 3G doesn't work out so well. A friend complained about the slowness and I recommended he try not restoring from backup and bingo, it was totally usable.