If you're using a Mac with Mail.app, you can enable it via iTunes to sync your mail account. This doesn't sync messages, just all the settings, including incoming and outbound mail servers. Have you tried this? This is how I initially set up my iPhone a while back and it's always worked.
On the bright side, I did the upgrade and lost no data, including my notes. And whenever my iPhone syncs, it saves a backup in iTunes. Not sure how to restore that backup, but it's there.