I've been pulling my hair out over this a few times already and FINALLY solved it. For me the issue seems that when my provider downloads all its settings to the phone the Internet service is called "Vodafone Live" where the email settings are trying to use "Internet" (which then no longer exists).
Just for future reference (mostly @myself), here is how to solve it:
At your mail inbox: Menu > Tools > Options > Click your email account > Edit Account Setup > press Next until you get to the Outgoing (SMTP) Mail server settings page > Click the Advanced Server Settings link at the bottom > change Network connection to your internet provider (Vodafone Live) instead of the default "Internet" > carry on through the pages until finished. It should now connect without the Error Synchronising message.