30/01/2012: Microsoft have recently deployed some changes which affects how mobile devices connects to Exchange.
Which versions are affected?
Devices running Android OS - Ice Cream Sandwich (version 4.x) and Gingerbread (version 2.3x).
If you're experiencing problems and your device is running one of the above versions of Android you will need to change the server address on your device as a temporary workaround.
1. Login to OWA and go to: Options > See All Options > Phone
2. You need to remove all listed devices. To do this select each device individually and click on the Delete button (button with an 'x' mark).
IMPORTANT: Do not select Wipe Device - this will delete all of your data!!!
3. You will now need to locate the new server address. Click on My Mail > question mark symbol (top right corner) and then About.
4. Look down the list until you see Host name. It will look something like: db3prd0104.outlook.com . This is the server address.
5. Back on the device, navigate to your mail settings and change the server address to the new address outlook.office365.com .