Yay, mine is working now! I did the "Restore settings" and now it's syncing again.
Recreating email accounts didn't help, but restoring settings did the job. Now it's a perfect phone again.