If you are restoring your settings from a non-jailbroken phone - or if you are not restoring at all - then you just need to reboot the phone first, and if that doesn't work, restore it.
If you are restoring from a jailbroken phone and it doesn't work, that's because you improperly set the permissions on the phone last time you fixed the problem in 1.1.3 or 1.1.4.
You probably followed some instructions that told you to chmod 755 or 777 on some files, when in fact the correct procedure would have been to chown them to mobile.mobile
So if you still have your old iPhone around, install SSH and SSH into the phone (username root, password alpine). Then type
cd /var/mobile/Library/Mail
chown mobile.mobile *
cd /var/private/Library/Mail
chown mobile.mobile *
Then connect the phone back to iTunes, rename it to something unique, and force it to make a backup (in Windows, you right click on the phone icon to do so).
Finally, connect the 3G iPhone and restore it as a backup (the name it suggests as the backup should be the unique name you chose above - if not, nuke your backup folder in iTunes and make a backup of the old iPhone again and repeat).