Recently had a user with a new Office 365 account receive the above error during downloading new email. Testing the connection it looks like the Wireless connection she was connecting to the internet with was intermittently slow.

Changing the Wifi to a hotspot or cable connection resolved this