The important thing to remember is that in Exchange 2013 Public Folders don't really exist like they used to. They're basically mailboxes.

In this particular scenario Public Folders were accessible internally, but not via Outlook Anywhere (or Outlook RPC over HTTPS if you're old).

This problem can manifests where the email address policy that applies to the Public Folder mailbox does not assign an email address that can be configured by autodiscover. i.e. publicfolder1@ad.contoso.com

The fix is to set the default address on the public folder to one where Autodiscover will work corrctly.

The easiest way to do this is either to manually set the primary SMTP address in the Active Directory attributes (email, and proxyaddresses), or alter your address list policies accordingly.

Now just wait for Outlook to pull the latest configuration. Or delete and recreate the profile if you're in a bit of a hurry.

More details are available under KB2788136.