You are running Microsoft Exchange Server 2013 in a coexistence environment together with either or both Microsoft Exchange Server 2010 or Exchange Server 2007.

Users are continuously prompted for their credentials or their mailboxes remain in a disconnected state. This problem may also affect Outlook Anywhere connections to Exchange Server 2010 or Exchange Server 2007 legacy public folders or Offline Address Books.

This is a known issue and a hotfix available from Microsoft.

See: http://support2.microsoft.com/kb/2990117

After installing the hotfix, reboot and test again.