Reset All Settings to fix slow iPhone 3G after iOS4 upgrade

Go to Settings | General | Reset | Reset All Settings.

This completely resolved the slow problem and all running great again for me.

I had done the phone reset as well (Press and hold the Sleep/Wake button and the Home button), so that might also need to be done, but in itself did not resolve the slow issue.