If you have data on the phone, like texts, emails, etc. your iPhone 3G will be unusable. Mine is also terrible, but I'll live with it until I make a fresh install when I buy an iPhone 4.
The problem is that it wasn't this slow with 3.x, yet I've really not gained any extra features, so it's basically a downgrade.