I had this problem and just used outlook help and figured it out...and it worked.
I had to activate the itunes outlook addin.
I have outlook 2010. I went to file, options, addins....and the itunes addin was in the inactive list. I highlighted it and then clicked go. and selected it to be active.
then you need to restart your computer and try to sync again. To sync, I used Itunes under the info tab and selected to sync my calendar and contacts.
I have spent HOURS on this and I am thrilled that it works.