Thought I'd add my own experience to this issue. Clean Win10 build 10162 install. Installed Office 2016 Preview. No previous office versions have been installed. Open Outlook and enter my email/password for our domain which is running on Office 365.
Setup works, emails download and continue to work while outlook remains open. Close outlook, open outlook and this error occurs. I tried deleting the profile and re-creating it but it is unable to connect. Restart computer, new profile is created successfully
and emails download. Close/re-open outlook and receive the error again.
I just double checked our autodiscover settings and they look fine. All other outlook versions are working fine and have been for some time. Just 2016 that doesn't work. And this is running on Microsofts own office 365 servers. And it obviously can connect
once. It just can't reconnect ever again after that.