Add2Exchange requires public folders, even for private-to-private synchronization.
Exchange 2003 always installs with Public Folder support and needs no further installation.
Exchange 2007 and 2010 must have public folder support installed. Public Folder support is installed during the initial Exchange 2010 setup when you enable Outlook 2003 support.
If you did not install Public Folder support during your Exchange install, see your Exchange documentation to enable Public Folder support.